官方题解｜投硬币

题目解析

问题的关键点是对于投完第 $i$ 枚硬币时，计数器为 $j$ 时可以得到的最大金额。

这个状态只和投完第 $i - 1$ 枚硬币时的状态有关。

于是对于投完第 $i$ 枚硬币，我们可以定义 $dp[i][j]$ 为投完第 $i$ 枚硬币后，计数器为 $j$ 可以获得的最大金额。

那么有 $dp[i][j] = \max{(dp[i][j], dp[i - 1][j - 1] + X_i + w_j)}$，其中 $w_j$ 为计数器为 $j$ 时，获得的额外奖金。

对于无法存在的状态，比如投完第 $i - 1$ 枚硬币后，无法令计数器为 $j$，那么便令 $dp[i - 1][j] = -\infty$。

另外在代码实现上我们只需要保存投 $i$ 枚硬币后的状态即可，所以只需要保留一维状态。

每次投完硬币后的状态数为 $\mathrm{O}(N)$；进行状态转移的复杂度为 $\mathrm{O}(N)$；总的时间复杂度为 $\mathrm{O}(N^2)$。

AC代码

C++ 代码：

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n);
    for (auto &x : a)
        std::cin >> x;
    std::vector<int> w(n + 1);
    for (int i = 0; i < m; ++i) {
        int c, y;
        std::cin >> c >> y;
        w[c] = y;
    }
    std::vector<i64> dp(n + 1, i64(-1e15));
    dp[0] = 0;
    for (auto &x : a) {
        i64 pre_max = *std::max_element(dp.begin(), dp.end());
        for (int i = n; i > 0; --i)
            dp[i] = std::max(dp[i], dp[i - 1] + x + w[i]);
        dp[0] = pre_max;
    }
    std::cout << *std::max_element(dp.begin(), dp.end()) << '\n';
    return 0;
}

Python 代码：

n, m = map(int, input().split())
a = list(map(int, input().split()))
w = [0] * (n + 1)
for i in range(m):
    c, y = map(int, input().split())
    w[c] = y
dp = [-10 ** 15] * (n + 1)
dp[0] = 0
for x in a:
    pre_max = max(dp)
    for i in range(n, 0, -1):
        dp[i] = max(dp[i], dp[i - 1] + x + w[i])
    dp[0] = pre_max
print(max(dp))