AcWing 6. 多重背包问题 III
原题链接
困难
作者:
长夜未央
,
2022-07-29 09:29:22
,
所有人可见
,
阅读 158
#include <iostream>
using namespace std;
const int N = 1010, M = 20010;
int n, m;
int v[N], w[N], s[N];
int f[2][M];
int q[M];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
// v体积,w价值,s个数
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i++) {
for (int j = 0; j < v[i]; j++) {
int hh = 0, tt = 0;
for (int k = j; k <= m; k += v[i]) {
f[i & 1][k] = f[i - 1 & 1][k];
if (hh < tt && q[hh] < k - s[i] * v[i]) hh++;
if (hh < tt)
f[i & 1][k] = max(f[i & 1][k], f[i - 1 & 1][q[hh]] + (k - q[hh]) / v[i] * w[i]);
while (hh < tt && f[i - 1 & 1][q[tt - 1]] - (q[tt - 1] - j) / v[i] * w[i] <= f[i - 1 & 1][k] - (k - j) / v[i] * w[i])
tt--;
q[tt++] = k;
}
}
}
cout << f[n & 1][m] << endl;
return 0;
}