多重背包单调队列

考虑思考完全背包问题的过程。完全背包其实是一个前缀最值的过程。而完全背包就是滑动窗口问题。可以把余数相同的归为一类，然后就可以直接单调队列了，队长 \(s\)。

#include<cstdio>
#define max(x,y) ((x)>(y)?(x):(y))
const int N=20001;
int n,m,f[N],g[N],q[N]; 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;++i){
		int v,w,s;
		scanf("%d%d%d",&v,&w,&s);
		for(int j=0;j<=m;++j)g[j]=f[j];
		for(int j=0;j<v;++j){//注意这个两重循环是 O(m)，因为每个余数都枚举到了，只是整合成一块了。
			int hh=0,tt=-1;
			for(int k=j;k<=m;k+=v){//单调队列优化
				if(hh<=tt&&q[hh]<k-s*v)++hh;
				if(hh<=tt)f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);
				while(hh<=tt&&g[q[tt]]-(q[tt]-j)/v*w<=g[k]-(k-j)/v*w)--tt; 
				q[++tt]=k;
			}
		}
	}
	printf("%d",f[m]);
	return 0;
}