数字货币交易网站开发怎么做,网站建设找金手指排名,多个网站建站,都江堰市网站建设题目#xff1a;
无聊中的小x玩起了Diablo I...
游戏的主人公有n个魔法 每个魔法分为若干个等级#xff0c;第i个魔法有p[i]个等级(不包括0) 每个魔法的每个等级都有一个效果值#xff0c;一个j级的i种魔法的效果值为w[i][j] 魔法升一级需要一本相应的魔法书 购买魔法书…题目
无聊中的小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个魔法 第i1行描述 第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 解题思路
这道题刚开始想了忒久然后终于做错了。后来经dalao一指点终于开窍原来那么简单。第一行可以用正常的分组背包接着后面的用一个数组记录
如b[选到的组数][所用的价格]选的等级。
然后递归返回就ok了╮(╯﹏╰╭是的吧。
然后一切尽在die代码中 代码这次就不用代码片了
#includecstdio #includeiostream using namespace std; int b[101][501],c[101],a[101][51],f[101][501],p[101],m,n,ss[501],x,y; bool flag; void print(int x,int y)//返回 { if (x0) return;//到第1个后返回 print(x-1,y-b[x][y]*c[x]);//递归回去 printf(%d\n,b[x][y]);//输出 } int main() { scanf(%d%d,n,m); for (int i1;in;i) { scanf(%d%d,c[i],p[i]); for (int j1;jp[i];j) { scanf(%d,a[i][j]); } } //以上输入依旧不解释 for (int i1;in;i) { for (int j1;jm;j) { f[i][j]f[i-1][j];//继承上一个 for (int k0;kp[i];k) { if (c[i]*kj) break;//如果当前的价值大于j了则可以退出了 if (f[i][j]f[i-1][j-c[i]*k]a[i][k])//如果找到更大的 { f[i][j]f[i-1][j-c[i]*k]a[i][k];//替换 b[i][j]k;//记录 } } } } printf(%d\n,f[n][m]);//输出最大值 for (int jm;j1;j--) for (int in;i1;i--)//注意递归顺序(⊙v⊙) if (f[i][j]f[x][y])//注意是不是 { xi; yj; }//寻找最大值让递归次数少些。
print(x,y);//看上面↑ for (int ix1;in;i) printf(0\n);//输出后面少的那些0 }
