WHYZOJ竞赛题目93:暗黑破坏神(01背包问题)
最编程
2024-01-14 19:30:23
...
【题目描述】:
无聊中的小x玩起了Diablo I... 游戏的主人公有n个魔法,每个魔法分为若干个等级,第i个魔法有p[i]个等级(不包括0)。每个魔法的每个等级都有一个效果值,一个j级的i种魔法的效果值为w[i][j]。魔法升一级需要一本相应的魔法书。购买魔法书需要金币,第i个魔法的魔法书价格为c[i]。
而小x只有m个金币(好孩子不用修改器)
你的任务就是帮助小x决定如何购买魔法书才能使所有魔法的效果值之和最大。开始时所有魔法为0级,效果值为0。
【输入描述】:
第一行,用空格隔开的两个整数n m;
以下n行,描述n个魔法;
第i+1行描述,第i个魔法 格式如下:
c[i] p[i] w[i][1] w[i][2] ... w[i][p[i]]
【输出描述】:
输出一个整数,即最大效果值。
【样例输入】:
【样例输出】:
【时间限制、数据范围及描述】:
时间:1s 空间:128M
0<n<=100
0<m<=500
0<p[i]<=50
0<c[i]<=10
保证输入数据和最终结果在longint范围内
这题叫真几把简单,就是一最基本的01背包,然而当时我还以为是什么高级的多重背包或者其他什么神奇的背包……感冒果然什么都搞不好啊QAQ