题解 | 秘藏

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;
int dp[200010][2][2];// 1 biao 1 li
void slove() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    for (int i = 1; i <= n; i++) std::cin >> b[i];
    dp[1][1][0] = dp[1][1][1] = a[1];
    if (dp[1][1][1] >= k)dp[1][1][1] -= k;
    else dp[1][1][1] = -1e9 - 10;
    dp[1][0][0] = dp[1][1][1];
    dp[1][0][1] = -1e9 - 10;
    for (int i = 2; i <= n; i++) {
        dp[i][1][0] = dp[i][1][1] = std::max(dp[i - 1][1][0], dp[i - 1][0][1]);
        dp[i][0][0] = dp[i][0][1] = std::max(dp[i - 1][0][0], dp[i - 1][1][1]);
        dp[i][1][0] += a[i];
        dp[i][0][0] += b[i];
        if (dp[i][1][0] >= k)dp[i][1][1] = dp[i][1][0] - k;
        else dp[i][1][1] = -1e9 - 10;
        if (dp[i][0][0] >= k)dp[i][0][1] = dp[i][0][0] - k;
        else dp[i][0][1] = -1e9 - 10;
    }
    int ans = std::max(dp[n][1][0], dp[n][0][0]);
    std::cout << ans << endl;
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T = 1;
    //std::cin>>T;
    while (T--)    {
        slove();
    }
    return 0;
}

最初始的dp，dp[i][0/1][0/1]代表到第i个位置，里/表世界是否花费金币颠倒的最大值。那么转移方程就很明显了，我们举一个例子：dp[i][0][0]就应该是从max(dp[i-1][0][0],dp[i-1][1][1])转移过来。书面语言就是里世界不花费金币的状态是从上一个里世界不花费金币颠倒（直接走）的状态和上一个表世界花费金币颠倒的状态中选一个得来。其他的同理，注意的是如果当前状态无法到达记得标记为-inf否则会影响后续状态。