$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

可参考： 滑动窗口

完整代码 $O(nm)$

#include<bits/stdc++.h>

using namespace std;

const int N = 20010;

int n,m;
int f[N]; //存储 f[i][j]
int g[N]; //存储 f[i-1][j]
int q[N]; //严格单调递减队列

int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;

        memcpy(g,f,sizeof f);

        for(int r=0;r<v;r++)
        {
            int hh=0,tt=-1;
            for(int j=r;j<=m;j+=v)
            {
                //判断队头是否出列
                if(hh<=tt&&q[hh]<j-s*v) hh++;

                //严格单调递减队列，队头就是最大值，滑动窗口中需要去掉偏移量
                while(hh<=tt&&g[q[tt]]-(q[tt]-r)/v*w<=g[j]-(j-r)/v*w) tt--;

                //放入队尾
                q[++tt]=j;

                //更新需要带上偏移量
                f[j]=g[q[hh]]+(j-q[hh])/v*w;
            }
        }
    }

    cout<<f[m]<<endl;

    return 0;
}