题解 | 秘藏

#include <functional>
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    int n,k;
    scanf("%d%d",&n,&k);
    vector<int>a(n);
    vector<int>b(n);
    for(int q=0;q<n;q++)
    {
        scanf("%d",&a[q]);
    }
        for(int p=0;p<n;p++)
    {
        scanf("%d",&b[p]);
    }
    vector<vector<long long>> f(n,vector<long long>(2,0));
    f[0][1]=a[0];
    f[0][0]=-1e9;
    for(int i=1;i<n;i++)
    {
        if(f[i-1][0]>=k)
        f[i][1]=max(f[i-1][1]+a[i],f[i-1][0]+a[i]-k);
        else f[i][1]=f[i-1][1]+a[i];
        if(f[i-1][1]>=k)
        f[i][0]=max(f[i-1][0]+b[i],f[i-1][1]+b[i]-k);
        else f[i][0]=f[i-1][0]+b[i];
    }
    printf("%lld",max(f[n-1][0],f[n-1][1]));
    return 0;
    }

暴力的dp，记住里世界第一个点不可到达就行。