多重背包问题有三种解法：

朴素版本时间复杂度O($$m*\sum S_{i}$$)

二进制优化时间复杂度O($$m*\sum log S_{i}$$) ，相对朴素版本低了一个数量级

但还不是最优，n=1000,si=1000时，会超时

那么就有单调队列+滚动数组的优化版本，时间复杂度O($$m*n$$)

如何想到用单调队列？

通过观察朴素版本，我们发现f[j]总是由f[j-v],f[j-v2]…f[j-vk]递推而来

也就是体积对V求模，同余的体积，总是大的由小的推导而来（这就是为什么我们这边为什么体积是从小到大来枚举）

仔细观察上图应该可以观察出这个规律

那么既然在体积为j时，我们需要在 [j-v*s,j-v] 这个区间内找一个最大值，而我们的体积j也是从小到大的

我们可以想到用单调队列来寻找区间内的最大值，查询的时间复杂度为O(1)，滚动的时间复杂度为O(m/v)

这样就能大大得降低我们的时间复杂度，减少不必要的状态计算

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=2e4+100;
//滚动数组为f和g
int f[M],g[M],n,m,q[M];
//单调队列优化
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        //g数组保存的是上一层的状态
        memcpy(g,f,sizeof f);
        //枚举每个余数，从0~v-1，同余与j的所有体积
        for(int j=0;j<v;j++)
        {
            int hh=0,tt=-1;//队头队尾
            for(int k=j;k<=m;k+=v)
            {
                if (hh<=tt&&q[hh]<k-s*v) ++hh;//如果队头掉出了区间，那么我们就删除队头
                //队头是当前区间内的最值，状态转移不用说，主要是要搞明白为什么价值是(k-q[hh])/v*w)
                //k是当前状态的体积，q[hh]表示队列内最值的下标，那么他们的差除以v就是取了几份物品
                if (hh<=tt)
                    f[k]=max(g[k],g[q[hh]]+(k-q[hh])/v*w);
                //当前物品优于队尾，那么就一直出队
                while(hh<=tt&&g[k]>=g[q[tt]]+(k-q[hh])/v*w) --tt;
                q[++tt]=k;
            }
        }
    }
    cout<<f[m];

    return 0;
}