1 条题解
-
0
思路: 根据题目要求,我们需要选择一种最优的属性组合来战胜所有的怪物,并且花费的金币数最少。首先,我们可以按照攻击力减去防御力的差值对怪物进行排序,使得勇士先攻击攻击力减去防御力较大的怪物。 然后,我们可以使用动态规划的思想来解决这个问题。定义一个二维数组dp,其中dp[i][j]表示勇士在前i只怪物中选择属性组合,并且花费不超过j金币时,能够战胜的最多怪物数量。 初始化dp数组的第一行和第一列为0,表示没有怪物或者金币数为0时,能够战胜的怪物数量为0。然后,我们可以使用一个双重循环来填充dp数组。对于每只怪物i,我们可以选择购买其攻击力或者防御力来增加勇士的属性。如果选择购买攻击力,花费的金币数为dp[i-1][j-Ai]+Ca,战胜的怪物数量为dp[i-1][j-Ai]+1;如果选择购买防御力,花费的金币数为dp[i-1][j-Di]+Cd,战胜的怪物数量为dp[i-1][j-Di]+1。我们选择花费金币数最少的方式,并更新dp[i][j]的值。 最后,我们可以遍历dp数组的最后一行,找到战胜所有怪物时花费金币数最少的属性组合。输出对应的生命值、攻击力和防御力即可,代码不用说了吧: (我这个不知道有没有毛病,希望各位大佬纠正👀)
- 1
信息
- ID
- 4141
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 1
- 已通过
- 1
- 上传者