牛客网 ACM 竞赛 65187 A 题：最大价值金币收集 - 动态规划解法

在一个古老的文明中，有一种神秘的金币。你是一名考古学家，偶然发现了这个文明的遗址，现在是时刻 0，有 n 枚金币同时被发现。第 i 枚金币会在 t'i' 时刻后消失，它的价值是 v'i'。然而，由于地形和其他条件的限制，你每个时刻只能收集一枚金币。此外，你的背包有限，你最多只能收集 k 枚金币。现在，你面前有 n 枚金币，你的任务是确定如何选择金币，以便在收集的金币数量不超过 k 的前提下，最大化你可以获取的金币价值总和。

注意：金币被收集到背包之后就不会消失了。

解法：动态规划

首先对金币按照存在时间进行排序，然后定义一个dp数组，dp[i][j]表示在前i个金币中选择最多j个金币所能获取的最大价值总和。

对于第i个金币，有两种情况：

1. 不选择第i个金币：此时dp[i][j] = dp[i-1][j]
2. 选择第i个金币：此时dp[i][j] = dp[i-1][j-1] + v[i]，其中v[i]表示第i个金币的价值

综上所述，状态转移方程为： dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + v[i])

最后返回dp[n][k]即可。

时间复杂度分析： 排序的时间复杂度为O(nlogn)，动态规划的时间复杂度为O(nk)，总时间复杂度为O(nklogn)。

空间复杂度分析： dp数组的大小为(n+1)*(k+1)，空间复杂度为O(nk)。

代码实现如下：