一道很好的单调队列优化多重背包入门题
令\(v[i]\)表示重量,\(w[i]\)表示价格 ,\(c[i]\)表示最多可放的数量,不难推出朴素的转移方程如下:
$f[i][j]=max\{f[i-1][j-k*v[i]]+k*w[i]\},j-k*v[i]\geqslant 0$
但这样时间复杂度太高了,令$r=j\%v[i],s=\left \lfloor \frac{j}{v[i]} \right \rfloor$考虑给转移方程变形为:
$f[i][j]=max\{f[i-1][r+k*v[i]]-k*w[i]\}+s*w[i],s-c[i]\leqslant k\leqslant s$
这个转移方程同样是正确的,并且我们发现取$max$的那一部分,在$r$确定的情况下,只跟$k$的值有关,于是我们就可以用单调队列优化啦。枚举$i$,$r$之后,对于每一个$r$我们开一个单调队列,扫一遍就好了
时间复杂度$O(nV)$
坑点:重量为$0$的物品要直接累加到答案中!
代码如下(懒得用滚动数组):
``` cpp
#include
using namespace std;
int n, m, zero, v[(int)1e5], w[(int)1e5], c[(int)1e5], f[105][(int)2e5];
struct S { //习惯开结构体QwQ
int id, w;
}q[(int)2e5];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> w[i] >> v[i] >> c[i];
for(int i = 1; i <= n; ++i) {
if(!v[i]) { //处理重量为0的物品
zero += w[i]c[i];
continue;
}
for(int r = 0, h = 0, t = 0; r < v[i]; ++r, h = t = 0) //h,t记得清零
for(int j = r, s = 0; j <= m; j += v[i], ++s) {
while(h < t && q[t-1].w < f[i-1][j]-sw[i]) --t; //--维护
q[t++] = S{s, f[i-1][j]-sw[i]}; //--队列
while(h < t && q[h].id < s-c[i]) ++h; //--单调性
f[i][j] = q[h].w+sw[i];
}
}
cout << zero+f[n][m];
return 0;
}