REALHW163 魔理沙的魔导书收纳

解题思路

这道题是反悔贪心 / DP 问题，核心难点在于：题目要求按顺序处理（不能重排），且挑战条件是当前魔力严格大于消耗值。

用 DP 求解：dp[i][k] 表示前 i 本书中成功挑战了 k 本时，能剩余的最大魔力值。值为 -1 表示该状态不可达。

状态转移：

• 跳过第 i 本：dp[i][k] = dp[i-1][k]
• 挑战第 i 本（需要 dp[i-1][k-1] > a[i-1]）：dp[i][k] = max(dp[i][k], dp[i-1][k-1] - a[i-1] + b[i-1])

最终从大到小找最大的 k 使得 dp[n][k] >= 0。

代码实现

e = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
n = len(a)

dp = [[-1] * (n + 1) for _ in range(n + 1)]
dp[0][0] = e

for i in range(1, n + 1):
    for k in range(n + 1):
        dp[i][k] = dp[i - 1][k]
        if k > 0 and dp[i - 1][k - 1] > a[i - 1]:
            dp[i][k] = max(dp[i][k], dp[i - 1][k - 1] - a[i - 1] + b[i - 1])

for k in range(n, -1, -1):
    if dp[n][k] >= 0:
        print(k)
        break

代码解析

以示例 E=18, a=[15,17,4,18], b=[1,15,4,17] 为例：

dp[i][k] 的含义：处理完前 i 本书、挑战了 k 本时，剩余的最大魔力。

第 1 本书 (a=15, b=1)：消耗大反馈少（净亏 14），跳过更优第 2 本书 (a=17, b=15)：dp[0][0]=18 > 17，挑战后剩 18-17+15=16第 3 本书 (a=4, b=4)：dp[2][1]=16 > 4，挑战后剩 16-4+4=16第 4 本书 (a=18, b=17)：dp[3][2]=16 ≯ 18，无法挑战

最终 dp[4][2]=16 >= 0，dp[4][3]=-1，所以最多挑战 2 本。

为什么存最大剩余魔力而非能否到达：同样挑战 k 本，剩余魔力越多越好，因为后续挑战需要魔力严格大于消耗值。存最大值保证不遗漏可行解。

复杂度分析

• 时间复杂度：O(n²)，n ≤ 100，最多 10000 次运算
• 空间复杂度：O(n²)，可滚动数组优化到 O(n)