题解 | 魔理沙的魔导书收纳

#include <climits>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    ll e;
    cin >> e;
    cin.ignore();
    vector<ll> a, b;
    int x;
    while (cin.peek() != '\n' && cin >> x)
        a.push_back(x);
    cin.ignore();
    while (cin.peek() != '\n' && cin >> x) 
        b.push_back(x);
    int n = a.size();
    vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, INT_MIN));
    dp[0][0] = e;
    for (int i = 1; i <= n; i++) {
        for (int k = 0; k <= i; k++) {
            dp[i][k] = dp[i - 1][k];
            if (k > 0 && 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 (int i = 0; i <= n; i++) {
    //     for (int j = 0; j <= n; j++) {
    //         cout << dp[i][j] << " " ;
    //     }
    //     cout << endl;
    // }
    int ans = 0;
    for (int k = n; k >= 0; k--)
        if (dp[n][k] >= 0) {
            ans = k;
            break;
        }
    cout << ans;
}
// 64 位输出请用 printf("%lld")

动态规划五部曲

1. 确定 dp 数组的下标及含义

dp[i][k] 是前 i 个结界刚好挑战了 k 个，剩余最大魔力值

2. 确定递推公式

处理第 i 个结界时，只有两种选择——跳过或者挑战。

• dp[i][k] = dp[i - 1][k];（跳过：魔力值不变）
• dp[i][k] = dp[i - 1][k - 1] - a[i - 1] + b[i - 1];（打：先扣再加）

选择"打"有一个前提条件：（魔力值必须严格大于该结界消耗值）。如果不满足这个条件，就只能跳过

dp[i][k] = dp[i - 1][k];
if (k > 0 && 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]);

3. dp 数组的初始化

• dp[0][0] = e，一本也没碰到时，魔力值为初始值。
• 其他初始化为INT_MIN，表示不可达

vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, INT_MIN));
dp[0][0] = e;

4. 确定遍历顺序

dp[i][k] 依赖于 dp[i - 1][k] 和 dp[i - 1][k - 1]，所以， i 和 k 都递增遍历即可。

5. 举例推导 dp 数组

找答案就看dp[n][k]中最大可达k，就是最多可以挑战的数量，即 k = 2，符合题意

性能分析

1. 时间复杂度

遍历求 dp[i][k]：O(m * n)

2. 空间复杂度

使用额外空间 dp 数组：O(m * n)