思路：考虑到之前的状态转移在遍历某个体积的倍数时，会有重复，所以可以用体积modv[i]得到v[i]类，对于每一类都是独立的，每个类之间互不影响，所以可以单独对每个类状态转移，而且容易发现每个类的每个体积j都可以构成一个等差数列，an=kv[i]+体积%v[i],所以实际上让前一个j每次加上一个v[i]即可，然后用单调队列维护最优解对应的下标，即：上一个状态的最大价值对应的下标（即：最大价值对应的体积）；
做法：用f[0][j]和f[1][j]滚动数组分别表示上一状态和当前状态下体积为j时的最优解，用q[]模拟单调队列，队头元素为最优解下的体积（即：f[][i]中的i），保证单调队列从head到rear对应的价值是单调递减的，即：队头元素始终对应最大值
时间：o（nv）
`

#include [HTML_REMOVED]

using namespace std;

const int maxn=2e4+2;

int f[2][maxn],q[maxn];

int main()

{

ios::sync_with_stdio(false);

cin.tie(0);

int n,m;

cin>>n>>m;

for(int i=1;i<=n;i++){

    int v,w,s;

    cin>>v>>w>>s;

    memcpy(f[0],f[1],sizeof(f[1]));//用当前状态f[1]去更新下一状态的上一个状态f[0]

    for(int j=0;j<v;j++){//遍历modv的余数，即从0到v-1，得到这v类

        int head=0,rear=-1;//head和rear分别表示单调队列的队头和队尾指针

        for(int k=j;k<=m;k+=v){//遍历当前这一类的每个体积，因为是公差为v的等差数列，所以依次+v即可

            f[1][k]=f[0][k];//每次先默认为上一个状态的最优解为最优解

            //接下来类似滑动窗口的操作:

            if(head<=rear&&k-s*v>q[head]){

                head++;//当前体积-限制能装的最大体积>最优解状态下的体积时（即：装不下当前的了），更新head，指向相对小一点的体积

            }

            if(head<=rear)

            {

                f[1][k]=max(f[0][k],f[0][q[head]]+(k-q[head])/v*w);//当前最优解等于当前默认最优解和选择装下当前个数的物品的最优解这两者的max

                //f[0][q[head]]即：上一个状态当前体积下的最优解,(k-q[head])/v即：个数，+(k-q[head])/v*w即：加上当前价值

            }

            while(head<=rear&&f[0][q[rear]]-(q[rear]-j)/v*w<=f[0][k]-(k-j)/v*w){//为了保证队列的单调递减性，如果当前体积下的价值大于等于队尾元素对应的价值时就要把之前队列中保存的价值<=当前价值的价值删去

                rear--;

            }

            q[++rear]=k;//每次把当前体积插入到队尾

        }

    }

}

cout<<f[1][m]<<endl;

return 0;

}`