背包问题

多重背包

单调队列优化 复杂度：O（N^2）

看f[j]的转移 从 $f[j-v]+w,f[j-2\cdot v]+2\cdot w,f[j-3\cdot v]+3\cdot w$ …….中的最大值转移
j体积都会与相同的模数转移过来，考虑枚举从0~v-1的模数，体积每次加v，不同的模数转移互不影响

const int M=200010;
int n,m;
int f[M],g[M],q[M];
void solve(){
	cin>>n>>m;//物品组数n,体积m
	for(int i=1;i<=n;i++){
		int c,w,s;
		cin>>c>>w>>s;//物品的体积，价值，个数
		memcpy(g,f,sizeof(f));
		for(int j=0;j<c;j++){
			int hh=0,tt=-1;
			for(int k=j;k<=m;k+=c){
				f[k]=g[k];
				if(hh<=tt&&k-c*s>q[hh])hh++;//当前队列里的个数为s个，需要弹出一个
				if(hh<=tt)f[k]=max(f[k],g[q[hh]]+(k-q[hh])/c*w);//从q[hh]到需要加上多少个w
				while(hh<=tt&&g[q[tt]]-(q[tt]-j)/c*w<=g[k]-(k-j)/c*w)tt--;//维护q[tt]>=k
				q[++tt]=k;
			}
  		}
	}
	cout<<f[m]<<'\n';
}