ABC261-D 解説

D - Flipping and Bonus

DPをします。$dp[$(0-indexedで)$i$回目のコイントスで$][j$回連続で表が出ているとき$]$のこれまでもらったお金の最大値 というDPができます。遷移は、$i$連続の連続ボーナスを$Bonus[i]$(なければ$0$)とすると、

$dp[i][0]=max(dp[i-1])$

$1 \le j \le i+1$のとき $dp[i][j]=dp[i-1][j-1]+X[i]+Bonus[j]$

で、答えは$max(dp[N-1])$です。

N, M = map(int, input().split())
X = list(map(int, input().split()))
Bonus = [0] * (N + 1)
for _ in range(M):
    C, Y = map(int, input().split())
    Bonus[C] = Y
dp = [[0] * (N + 1) for _ in range(N)]
dp[0][1] = X[0] + Bonus[1]
for i in range(1, N):
    dp[i][0] = max(dp[i - 1])
    for j in range(1, i + 2):
        dp[i][j] = dp[i - 1][j - 1] + X[i] + Bonus[j]
print(max(dp[N - 1]))

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> X(N);
    for (int i = 0; i < N; i++) {
        cin >> X[i];
    }
    vector<int> Bonus(N + 1);
    for (int i = 0; i < M; i++) {
        int C, Y;
        cin >> C >> Y;
        Bonus[C] = Y;
    }
    vector<vector<long long>> dp(N, vector<long long>(N + 1));
    dp[0][1] = X[0] + Bonus[1];
    long long mx = dp[0][1];
    for (int i = 1; i < N; i++) {
        dp[i][0] = mx;
        for (int j = 1; j <= i + 1; j++) {
            dp[i][j] = dp[i - 1][j - 1] + X[i] + Bonus[j];
            if (mx < dp[i][j]) {
                mx = dp[i][j];
            }
        }
    }
    cout << mx << '\n';
}