1 条题解

  • 0
    @ 2023-9-3 18:15:42

    思路: 根据题目要求,我们需要选择一种最优的属性组合来战胜所有的怪物,并且花费的金币数最少。首先,我们可以按照攻击力减去防御力的差值对怪物进行排序,使得勇士先攻击攻击力减去防御力较大的怪物。 然后,我们可以使用动态规划的思想来解决这个问题。定义一个二维数组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数组的最后一行,找到战胜所有怪物时花费金币数最少的属性组合。输出对应的生命值、攻击力和防御力即可,代码不用说了吧: image (我这个不知道有没有毛病,希望各位大佬纠正👀)

    • 1

    信息

    ID
    4141
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    1
    已通过
    1
    上传者