企业管理培训课程排行榜,企业seo解决方案,wordpress标签链接优化,广州抖音seo价格暗黑破坏神#xff08;ssl 2295#xff09;
Description
无聊中的小x玩起了Diablo I... 游戏的主人公有n个魔法 每个魔法分为若干个等级#xff0c;第i个魔法有p[i]个等级(不包括0) 每个魔法的每个等级都有一个效果值#xff0c;一个j级的i种魔法的效果值为w[i][j] 魔法升… 暗黑破坏神ssl 2295
Description
无聊中的小x玩起了Diablo I... 游戏的主人公有n个魔法 每个魔法分为若干个等级第i个魔法有p[i]个等级(不包括0) 每个魔法的每个等级都有一个效果值一个j级的i种魔法的效果值为w[i][j] 魔法升一级需要一本相应的魔法书 购买魔法书需要金币第i个魔法的魔法书价格为c[i] 而小x只有m个金币(好孩子不用修改器) 你的任务就是帮助小x决定如何购买魔法书才能使所有魔法的效果值之和最大 开始时所有魔法为0级 效果值为0
Input
第一行 用空格隔开的两个整数n(0n100) br m(0m500) 以下n行 描述n个魔法 第i1行描述 第i个魔法 格式如下(0p[i]50, br 0c[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 Hint
0 n 100,0 m 500,0 p[i] 50,0 c[i] 10
解题方法
分组改一改输出最大效果后用递归输出第几个.(注意输出要换行)
代码 #includeiostream
using namespace std;
int n,m,a[1001][1001],p[1001],c[1001],b[1001][1001],f[6001][6001],x,y;
void sj(int x,int y) //递归输出第几个魔法
{
if (x0) return;
sj(x-1,y-b[x][y]*c[x]);
coutb[x][y]\n;
}
int main()
{
cinnm;
for (int i1;in;i){cinc[i]p[i];for (int j1;jp[i];j)cina[i][j];}
for (int i1;in;i)for (int j1;jm;j){f[i][j]f[i-1][j]; for (int o0;op[i];o){if (c[i]*oj) break; //判断有没有越界if (f[i][j]f[i-1][j-c[i]*o]a[i][o]){f[i][j]f[i-1][j-c[i]*o]a[i][o]; //找到跟大的就换b[i][j]o; //记录}}}
coutf[n][m]\n;
for (int jm;j1;j--)
for (int in;i1;i--)if (f[i][j]f[x][y]){xi;yj;}sj(x,y);for(int ix1;in;i) cout0endl; //输出少的0
}
