WHYZOJ-#93. 暗黑破壞神(垃圾01背包)

【題目描述】：

無聊中的小x玩起了Diablo I... 遊戲的主人公有n個魔法，每個魔法分為若幹個等級，第i個魔法有p[i]個等級(不包括0)。每個魔法的每個等級都有一個效果值，一個j級的i種魔法的效果值為w[i][j]。魔法升一級需要一本相應的魔法書。購買魔法書需要金币，第i個魔法的魔法書價格為c[i]。

而小x隻有m個金币(好孩子不用修改器)

你的任務就是幫助小x決定如何購買魔法書才能使所有魔法的效果值之和最大。開始時所有魔法為0級，效果值為0。

【輸入描述】：

第一行，用空格隔開的兩個整數n m；

以下n行，描述n個魔法；

第i+1行描述，第i個魔法 格式如下：

c[i] p[i] w[i][1] w[i][2] ... w[i][p[i]]

【輸出描述】：

輸出一個整數，即最大效果值。

【樣例輸入】：

3 10
1 3 1 2 2
2 3 2 4 6
3 3 2 1 10      

【樣例輸出】：

11      

【時間限制、資料範圍及描述】：

時間：1s 空間：128M

0<n<=100

0<m<=500

0<p[i]<=50

0<c[i]<=10

1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAX=505;
 5 int n,m;
 6 int c[MAX],p[MAX],w[MAX][MAX]={0};
 7 int f[MAX][MAX];
 8 inline int read(){
 9     int an=0,x=1;char c=getchar();
10     while (c<'0' || c>'9') {if (c=='-') x=-1;c=getchar();}
11     while (c>='0' && c<='9') {an=an*10+c-'0';c=getchar();}
12     return an*x;
13 }
14 int main(){
15     freopen ("godness.in","r",stdin);
16     freopen ("godness.out","w",stdout);
17     int i,j,k;
18     n=read();m=read();
19     for (i=1;i<=n;i++){
20         c[i]=read(),p[i]=read();
21         for (j=1;j<=p[i];j++){
22             w[i][j]=read();
23         }
24     }
25     memset(f,0,sizeof(f));
26     for (i=1;i<=n;i++){
27         for (j=0;j<=p[i];j++){
28             for (k=m;k>=c[i]*j;k--){
29                 f[i][k]=max(f[i][k],f[i-1][k-c[i]*j]+w[i][j]);
30             }
31         }
32     }
33     printf("%d",f[n][m]);
34     return 0;
35