洛谷P1776 宝物筛选

一道很好的单调队列优化多重背包入门题

令\(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]-s
w[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+s
w[i];

}

}

cout << zero+f[n][m];

return 0;

}

上一篇:python+selenium生成测试报告后自动发送邮件


下一篇:[Spring boot] Application properties and configurations