更新日志
2025/11/14：开工。思路
我怎么现在才会这个？？
以前的时候看那些题解写得很高级很复杂，现在真感觉，唉。
不难发现因为你只能选整个物品，每次状态转移多出的体积只会是 \(w_i\) 的倍数，因此只有模 \(w_i\) 同余的状态才能转移。直接把每个余数拉出来跑一遍即可，由于个数限制所以每次都是求后缀最大值，单调队列优化一下就做完了。复杂度 \(O(nV)\)。
例题
宝物筛选
代码
int n,m;
int v[N],w[N],c[N];
ll f[M];
pil q[M];int hd,tl;inline void Main(){cin>>n>>m;rep(i,1,n)cin>>v[i]>>w[i]>>c[i];rep(i,1,n)repl(j,0,w[i]){hd=1,tl=0;rep(k,0,(m-j)/w[i]){ll vl=f[k*w[i]+j]-k*v[i];while(hd<=tl&&q[tl].sec<vl)--tl;q[++tl]={k,vl};while(hd<=tl&&k-q[hd].fir>c[i])++hd;f[k*w[i]+j]=q[hd].sec+k*v[i];}}put(f[m]);
}