C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int dp[N],g[N],q[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;++i){
        int v,w,s;cin>>v>>w>>s;
        if(s==0){
            for(int j=0;j<=m;++j){
                if(j>=v)dp[j]=max(dp[j],dp[j-v]+w);
            }
        }else if(s==-1){
            for(int j=m;j>=0;--j){
                if(j>=v)dp[j]=max(dp[j],dp[j-v]+w);
            }
        }else{
//          for(int j=m;j>=0;--j){                        //超时 1000+ 
//              for(int k=1;k<=s&&k*v<=j;++k){
//                  dp[j]=max(dp[j],dp[j-k*v]+w*k);
//              }
//          }
            memcpy(g,dp,sizeof(dp));
            for(int j=0;j<v;++j){
                int hh=0,tt=-1;
                for(int k=j;k<=m;k+=v){
                    if(tt>=hh && q[hh]<k-v*s)hh++;
                    while(tt>=hh && g[k]>=g[q[tt]]+(k-q[tt])/v*w)tt--;
                    if(tt>=hh)dp[k]=max(g[k],g[q[hh]]+(k-q[hh])/v*w);
                    q[++tt]=k;
                }
            }
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}