yls曾经说过如果你理解不了，就是其中省了步骤；
yls还说过背包问题的优化都是在代码的基础上进行的优化

所以我先用了二维数组去解决这个问题，然后再优化到一维（但是因为滑动窗口的原因不能让j从大到小循环）

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010,M=20010;
int v[N],w[N],s[N];
int f[N][M],q[M];//q数组记得是下标,因为q数组是记得f[i][j]中的j，所以q的大小是跟M一样大
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<v[i];j++){
            int tt=0,hh=0;
            for(int k=j;k<=m;k+=v[i]){
                if(hh<tt&&q[hh+1]<k-s[i]*v[i])hh++;
                // f[i][k]=f[i-1][k];
                // if(tt>hh)f[i][k]=max(f[i-1][k],f[i-1][q[hh+1]]+(k-q[hh+1])/v[i]*w[i]);
                //如果二维要放在加入第k位的工作的前面要加上这一步，因为可能滑动窗口里没有数但是你要更新，所以要把f[i-1][j]赋给f[i][j]。
                while(tt>hh&&f[i-1][q[tt]] + (k - q[tt]) / v[i] * w[i] <= f[i-1][k]) tt--;
                q[++tt]=k;
                if(tt>hh)f[i][k]=max(f[i-1][k],f[i-1][q[hh+1]]+(k-q[hh+1])/v[i]*w[i]);
            }
        }
    cout<<f[n][m]<<endl;
    return 0;
}

然后就是一维的代码就是yls课上写的那样

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=20010;
int f[M],q[M],g[M];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int v,w,s;
        cin>>v>>w>>s;
        memcpy(g,f,sizeof f);
        for(int j=0;j<v;j++){
            int tt=0,hh=0;
            for(int k=j;k<=m;k+=v){
                if(tt>hh&&q[hh+1]<k-s*v) hh++;
                if(tt>hh) f[k]=max(g[k],g[q[hh+1]]+(k-q[hh+1])/v*w);
                while(hh<tt&&g[q[tt]]+(k-q[tt])/v*w<=g[k])tt--;
                q[++tt]=k;
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}