题解 | 秘藏

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
ll a[N];
ll b[N];
ll dp[N][2];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    dp[1][0]=a[1];
    dp[1][1]=0;
    for(int i=2;i<=n;i++)
    {
        if(dp[i-1][0]>=k)dp[i][1] = max(dp[i-1][1],dp[i-1][0]-k)+b[i];
        else if(dp[i-1][1]!=0)dp[i][1] = dp[i-1][1]+b[i];
        if(dp[i-1][1]>=k)dp[i][0] = max(dp[i-1][0],dp[i-1][1]-k)+a[i];
        else dp[i][0] = dp[i-1][0]+a[i];
    }
    ll ans = max(dp[n][0],dp[n][1]);
    cout<<ans<<'\n';
    return 0;
}

时间复杂度O(n)，dp，dp[i][0]表示在i号点的表世界能获得的最大收益，dp[i][1]表示在里世界能获得的最大收益，唯一需要注意的点是，只有魔法师能够到达里世界，我们才进行里世界的状态转移，所以我加了个else if语句，不等于0表示进入过dp[i-1][1]里面了，这时候我们就进行状态转移