暗黑破坏神"/>
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;
}
更多推荐
SSLOJ2295暗黑破坏神
发布评论