SSL
暗黑破坏神
题目
无聊中的小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<=100)m(0<m<=500)
以下n行描述n个魔法
第i+1行描述第i个魔法格式如下(0<p[i]<=50, 0<c[i]<=10)
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
解析
这题经过修改后可以变成一个分组背包，倒也能做，但是该题有两大槽点：
1：路径不开SPJ，搞得人心态崩掉
2：数据范围写的是n<=100，但n开110WA，开210就能AC
总结：一道破题
code:
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,c[210],v[210][210],w[210][510],dp[210][510],p[210][510],q[210][510],t,mx=0;
void print(int x,int y)//递归输出方案
{if(x==0)return;print(x-1,p[x][y]);printf("%d\n",q[x][y]);return;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d%d",&t,&c[i]);for(int j=1;j<=c[i];j++)scanf("%d",&v[i][j]),w[i][j]=j*t;//转分组背包}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(dp[i][j]<dp[i-1][j-w[i][k]]+v[i][k])//分组背包{dp[i][j]=dp[i-1][j-w[i][k]]+v[i][k];p[i][j]=j-w[i][k];q[i][j]=k;}for(int i=0;i<=m;i++)if(dp[n][i]>mx){t=i;mx=dp[n][i];}printf("%d\n",mx);print(n,t);return 0;
}
发布评论