问题陈述：给定一组n个不同面额的硬币(可能重复，按随机顺序(和一个数字k。单个玩家按照以下方式玩游戏：玩家可以选择连续挑选0到k个硬币，但必须留下下一个硬币。通过这种方式，他/她可以收集到最高数量的硬币。
输入：第一行分别包含2个空格分隔的整数n和x，表示n-阵列的大小x-窗口大小
输出：表示玩家可以获得的最大和的单个整数。
工作解决方案链接：Ideone
long long solve(int n, int x) {
if (n == 0) return 0;
long long total = accumulate(arr + 1, arr + n + 1, 0ll);
if (x >= n) return total;
multiset<long long> dp_x;
for (int i = 1; i <= x + 1; i++) {
dp[i] = arr[i];
dp_x.insert(dp[i]);
}
for (int i = x + 2; i <= n; i++) {
dp[i] = arr[i] + *dp_x.begin();
dp_x.erase(dp_x.find(dp[i - x - 1]));
dp_x.insert(dp[i]);
}
long long ans = total;
for (int i = n - x; i <= n; i++) {
ans = min(ans, dp[i]);
}
return total - ans;
}
有人能解释一下这个代码是如何工作的吗？也就是说，Ideone解决方案中的第12-26行是如何产生正确答案的？
我用笔和纸对代码进行了试运行，发现它给出了正确的答案，但无法计算出使用的算法(如果有的话(。有人能向我解释一下12-26号线是如何得出正确答案的吗？这里有什么技术或算法在用吗？
我是DP的新手，所以如果有人能指出与这类问题有关的教程(YouTube视频等(，那也太好了。非常感谢。
这个想法似乎是在转换问题-您必须在连续不超过x+1个硬币中至少选择一个硬币，并使其最小化。那么原来问题的答案就是[所有值的总和]-[新问题的答案]。
然后我们准备讨论动态编程。让我们定义CCD_ 2的递推关系；考虑第一到第i个硬币和第i个货币的新问题的部分答案被选择"；。(很抱歉描述不正确，欢迎编辑(
f(i) = a(i) : if (i<=x+1)
f(i) = a(i) + min(f(i-1),f(i-2),...,f(i-x-1)) : otherwise
where a(i) is the i-th coin value
我逐行添加了一些评论。
// NOTE f() is dp[] and a() is arr[]
long long solve(int n, int x) {
if (n == 0) return 0;
long long total = accumulate(arr + 1, arr + n + 1, 0ll); // get the sum
if (x >= n) return total;
multiset<long long> dp_x; // A min-heap (with fast random access)
for (int i = 1; i <= x + 1; i++) { // For 1 to (x+1)th,
dp[i] = arr[i]; // f(i) = a(i)
dp_x.insert(dp[i]); // Push the value to the heap
}
for (int i = x + 2; i <= n; i++) { // For the rest,
dp[i] = arr[i] + *dp_x.begin(); // f(i) = a(i) + min(...)
dp_x.erase(dp_x.find(dp[i - x - 1])); // Erase the oldest one from the heap
dp_x.insert(dp[i]); // Push the value to the heap, so it keeps the latest x+1 elements
}
long long ans = total;
for (int i = n - x; i <= n; i++) { // Find minimum of dp[] (among candidate answers)
ans = min(ans, dp[i]);
}
return total - ans;
}
还请注意，multiset用作最小堆。然而，我们也需要快速随机访问(擦除旧的(，multiset可以在对数时间内完成。因此，总的时间复杂度为O(n log x)。