[BZOJ 5390]: [Lydsy1806月赛]糖果商店

设f[i][j]表示总质量为i,最上层糖果种类为j的最优方案。g[i]表示总质量为i的最优方案。
每次只能将最上层添加一颗糖果或者添加一层新的糖果。
转移方程可以看代码。
 1 #include<queue>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<algorithm>
 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 }
View Code
原文地址:https://www.cnblogs.com/xuruifan/p/9294070.html