题解 | 秘藏

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

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<ll> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    
    vector<vector<ll>> dp(n + 1, vector<ll>(2, -1e18));
    dp[1][0] = a[1];  // 起始在表世界1号点
    
    for (int i = 2; i <= n; i++) {
        // 从表世界 i-1 走到表世界 i
        if (dp[i - 1][0] != -1e18) {
            dp[i][0] = max(dp[i][0], dp[i - 1][0] + a[i]);
        }
        
        // 从里世界 i-1 走到里世界 i
        if (dp[i - 1][1] != -1e18) {
            dp[i][1] = max(dp[i][1], dp[i - 1][1] + b[i]);
        }
        
        // 从表世界 i-1 跃迁到里世界 i
        if (dp[i - 1][0] != -1e18 && dp[i - 1][0] >= k) {
            dp[i][1] = max(dp[i][1], dp[i - 1][0] - k + b[i]);
        }
        
        // 从里世界 i-1 跃迁到表世界 i
        if (dp[i - 1][1] != -1e18 && dp[i - 1][1] >= k) {
            dp[i][0] = max(dp[i][0], dp[i - 1][1] - k + a[i]);
        }
    }
    
    cout << max(dp[n][0], dp[n][1]) << endl;
    
    return 0;
}

动态规划