BZOJ1775[USACO 2009 Dec Gold 3.Video Game Troubles]——DP

 1 #include<queue>
 2 #include<cmath>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<algorithm>
 7 using namespace std;
 8 int n,m;
 9 int x,y;
10 int v,c;
11 int g[51][100010];
12 int f[51][100010];
13 int main()
14 {
15     scanf("%d%d",&n,&m);
16     memset(g,0x80,sizeof(g));
17     memset(f,0x80,sizeof(f));
18     for(int i=0;i<=m;i++)
19     {
20         g[0][i]=f[0][i]=0;
21     }
22     for(int i=1;i<=n;i++)
23     {
24         scanf("%d%d",&v,&c);
25          
26         for(int j=0;j<=m;j++)
27         {
28             f[i][j]=max(f[i-1][j],g[i-1][j]);
29             if(v<=j)
30             {
31                 g[i][j]=max(g[i-1][j-v],f[i-1][j-v]);
32             }
33         }
34         while(c--)
35         {
36             scanf("%d%d",&x,&y);
37             for(int j=m;j>=v;j--)
38             {
39                 g[i][j]=max(g[i][j],g[i][j-x]+y);
40             }
41         }
42     }
43     printf("%d",max(f[n][m],g[n][m]));
44 }