题解 | 秘藏

dp 初始下开始情况

有四种前进的情况

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    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,-1));
    dp[1][0]=a[1];
    dp[1][1]=-1;
    for(int i=2;i<=n;i++){
        if(dp[i-1][0]!=-1){
            dp[i][0]=max(dp[i][0],dp[i-1][0]+a[i]);
        }
        if(dp[i-1][1]!=-1&&dp[i-1][1]>=k){
            dp[i][0]=max(dp[i][0],dp[i-1][1]-k+a[i]);
        }
        if (dp[i-1][1]!=-1){
            dp[i][1]=max(dp[i][1],dp[i-1][1]+b[i]);
        }
        if (dp[i-1][0]!=-1&&dp[i-1][0]>=k){
            dp[i][1]=max(dp[i][1],dp[i-1][0]-k +b[i]);
    
    }}
    cout<<max(dp[n][1],dp[n][0]);
    return 0;
}
// 64 位输出请用 printf("%lld")