【题意】
多重背包问题，每种物品有限制个数
【分析】
做点分治的时候突然发现竟然不会单调队列优化多重背包，于是就跑来做这个绿题了
我们有二进制分组的$O(\sum_{i=1}^nlog(num[i])$
其实还有优秀的$O(nv)$做法
我们考虑转移方程$f[i][j]=max(f[i?1][j?w?k]+v?k) (k<=c)$
把它写成$f[i][j]=max(f[i?1][d+w?k]?v?k)+v?s (s-k<=c)$这种形式，其中d为 j mod w[i] ，s为 j/w[i]
这样我们就显然可以对于各个余数做一下单调队列了
【代码】
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=4e4+5; int q[maxn],f[maxn],pos[maxn]; int head,tail,n,W; int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d%d",&n,&W); int v,w,c,ans=0; for(int i=1;i<=n;i++) { scanf("%d%d%d",&v,&w,&c); if(!w) {ans+=c*v; continue;} int gs=W/w; c=min(c,gs); for(int d=0;d<w;d++) { head=tail=0; gs=(W-d)/w; for(int j=0;j<=gs;j++) { while(head<tail && f[d+j*w]-j*v>=q[tail-1]) tail--; pos[tail]=j; q[tail++]=f[d+j*w]-j*v; while(head<tail && pos[head]<j-c) head++; f[d+j*w]=max(f[d+j*w],q[head]+j*v); } } } printf("%d",ans+f[W]); return 0; }