题意

给定 天的安排，每天有两种选择：

  1. 学习：获得 点知识，压力值增加 。
  2. 做博丽灵梦：不获得知识，压力值减少 （减后若为负则视为 ）。

初始压力值为 ，要求在每一天结束后，压力值都必须满足 。求 天后能获得的最大知识量。

题解

既然涉及每天的决策，并且由于数据范围较小（），很显然可以利用**动态规划（DP）**来求解。

我们考虑将当前的“压力值”作为状态。设 表示在某一天的决策结束后，压力值恰好为 时所能获得的最大知识量。初始时，第 天 ，其余状态由于无法到达，设为一个极小值（如 ）。

对于第 天，我们枚举前一天的所有可能的合法压力值 ，并尝试进行转移：

  1. 如果选择学习：这会使得压力值增加 。我们需要判断 是否超过了上限 。如果 ，则可以用新获得的知识量来更新后续的状态：
  2. 如果选择做博丽灵梦：这会使得压力值减少 。由于题目特别说明了“减为负数则视为 ”，所以决策后的新压力值为 。此时知识量不会增加：

每天计算完毕后，将 滚动替换掉 数组即可。最终答案即为 天结束后，所有有效状态 中的最大值。

复杂度

  • 时间复杂度:
  • 空间复杂度:

参考代码与链接

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];

    vector<long long> dp(m + 1, -1);
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
        vector<long long> ndp(m + 1, -1);
        for (int j = 0; j <= m; ++j) {
            if (dp[j] == -1) continue;

            // 选择学习
            if (j + b[i] <= m) {
                ndp[j + b[i]] = max(ndp[j + b[i]], dp[j] + a[i]);
            }
            // 选择做博丽灵梦
            int nj = max(0LL, j - b[i]);
            ndp[nj] = max(ndp[nj], dp[j]);
        }
        dp = move(ndp);
    }

    long long ans = 0;
    for (int j = 0; j <= m; ++j) {
        ans = max(ans, dp[j]);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
}