AcWing 6. 多重背包问题 III
原题链接
困难
作者:
心向远方
,
2021-05-10 19:00:07
,
所有人可见
,
阅读 7
#include <bits/stdc++.h>
#pragma GCC optimize(2)
int N, V;
int f[20001], g[20001], q[20001];
int mp[20001];
int main() {
scanf("%d%d", &N, &V);
for (int i = 1; i <= N; i++) {
int v, w, s;
scanf("%d%d%d", &v, &w, &s);
memcpy(g, f, sizeof f);
for (int j = 0; j < v; j++) {
int cnt = 0;
// 维护一个长度为s[i] + 1 的单调队列
int tail = -1, head = 0;
for (int k = j; k <= V; k += v, cnt++) {
mp[cnt] = k;
g[k] -= w * cnt;
while (head != tail + 1 && g[mp[q[tail]]] <= g[k])
tail--;
q[++tail] = cnt;
while (head != tail + 1 && q[head] < cnt - s)
head++;
f[k] = g[mp[q[head]]] + cnt * w;
}
}
}
printf("%d", f[V]);
return 0;
}