AcWing 6. 多重背包问题 III-待解决
原题链接
困难
作者:
rushhhhh
,
2021-02-17 16:02:10
,
所有人可见
,
阅读 406
#include <iostream>
#include <cstring>
using namespace std;
// https://www.acwing.com/solution/content/6500/
const int N = 20010;
// pre和dp存的是一个东西:最大价值
// q队列是max()中的dp[]内的下标
// 从公式可知,q可推出dp
int dp[N], pre[N], q[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
memcpy(pre, dp, sizeof(dp));
int v, w, s;
cin >> v >> w >> s;
for (int j = 0; j < v; ++j) {
int head = 0, tail = -1;
for (int k = j; k <= m; k += v) {
// 要取窗口内的最大值,所用队列为单调递减队列
// 如果单调队列的队头在滑动窗口的左侧(外面)
// 并不是直接丢弃,而是上个for循环已经使用了这一元素
// k-s*v为窗口左侧的位置,q[head]为队首元素(是坐标)
if (head <= tail && k - s*v > q[head])
++head;
// 判断队尾元素是否还有效
// 比较队尾元素对应的dp值和当前下标k对应的dp值
while (head <= tail && (pre[q[tail]] - (q[tail] - j)/v * w) <= (pre[k] - (k - j)/v * w))
--tail;
// 当前元素入队
q[++tail] = k;
// 若队列中有元素,取队首元素,是最大值,更新dp
if (head <= tail)
dp[k] = max(dp[k], pre[q[head]] + (k - q[head])/v * w);
}
}
}
cout << dp[m] << endl;
return 0;
}