设f[i][j]表示总质量为i，最上层糖果种类为j的最优方案。g[i]表示总质量为i的最优方案。

每次只能将最上层添加一颗糖果或者添加一层新的糖果。

转移方程可以看代码。

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #define N 105 6 #define M 100010 7 #define ll long long 8 using namespace std; 9 char ch,B[1<<15],*S=B,*T=B;10 #define getc() getchar()//(S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)11 inline int read()12 {13     int x=0,f=1;char ch=getc();14     while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1;ch=getc();}15     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}16     return x*f;17 }18 int n,m,d[M],w[N],v[N],l[N];19 ll f[M][N],g[M],ans;20 int main()21 {22     n=read();m=read();23     for(int i=1;i<=m;i++)d[i]=read();24     for(int i=1;i<=n;i++)25     {26         w[i]=read();27         v[i]=read();28         l[i]=read();29     }30     g[0]=0;31     for(int j=1;j<=n;j++)f[0][j]=-1e18;32     for(int i=1;i<=m;i++)33     {34         g[i]=-1e18;35         for(int j=1;j<=n;j++)36         {37             f[i][j]=-1e18;38             if(i>=(ll)w[j]*l[j])39                 f[i][j]=g[i-(ll)w[j]*l[j]]+(ll)v[j]*l[j]-d[i-w[j]*l[j]];40             if(i>=w[j])41                 f[i][j]=max(f[i][j],f[i-w[j]][j]+v[j]);42             g[i]=max(g[i],f[i][j]);43         }44         ans=max(ans,g[i]);45         printf("%lld ",ans);46     }47 }