SSLOJ2295暗黑破坏神

暗黑破坏神"/>

SSLOJ2295暗黑破坏神

Description

无聊中的小x玩起了Diablo I…

游戏的主人公有n个魔法

每个魔法分为若干个等级，第i个魔法有p[i]个等级(不包括0)

每个魔法的每个等级都有一个效果值，一个j级的i种魔法的效果值为w[i][j]

魔法升一级需要一本相应的魔法书

购买魔法书需要金币，第i个魔法的魔法书价格为c[i]

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

你的任务就是帮助小x决定如何购买魔法书才能使所有魔法的效果值之和最大

开始时所有魔法为0级 效果值为0

Input

第一行 用空格隔开的两个整数n(0

以下n行 描述n个魔法

第i+1行描述 第i个魔法 格式如下(0

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

Output

第一行输出一个整数，即最大效果

Sample Input

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

Sample Output

11
1
0
3

思路

设f[i][j]为前i种魔法用j金币的最大效果
f [ i ] [ j ] = f [ i − 1 ] [ j − w [ i ] [ k ] ] + v [ i ] [ k ] ] ( 1 < = i < = n , 0 < = k < = c [ i ] , m > = j > = w [ i ] [ k ] ) f[i][j]=f[i-1][j-w[i][k]]+v[i][k]](1<=i<=n,0<=k<=c[i],m>=j>=w[i][k]) f[i][j]=f[i−1][j−w[i][k]]+v[i][k]](1<=i<=n,0<=k<=c[i],m>=j>=w[i][k])
code:

#include<iostream>
#include<cstdio>
using namespace std;
int v[205][205],w[205][205],f[200][600],c[205],q[200][600],p[200][600];
void print(int x,int y)
{if (x==0) return;print(x-1,q[x][y]);cout<<p[x][y]<<endl;return;
}
int main()
{int n,m;cin>>n>>m;for (int i=1;i<=n;i++){int x;cin>>x>>c[i];for (int j=1;j<=c[i];j++){w[i][j]=j*x;cin>>v[i][j];}}for (int i=1;i<=n;i++){for (int k=0;k<=c[i];k++){for (int j=m;j>=w[i][k];j--){if (f[i][j]<f[i-1][j-w[i][k]]+v[i][k]){f[i][j]=f[i-1][j-w[i][k]]+v[i][k];q[i][j]=j-w[i][k];p[i][j]=k;}}}}int mx=0,mxy;for (int j=0;j<=m;j++){if (mx<f[n][j]){mx=f[n][j];mxy=j;}}cout<<mx<<endl;print(n,mxy);return 0;
}