由于不知道最后是从哪个出口出来的,所以状态数组为二维,维护两个世界dp[3][200010]
每个位置由当前世界推移过来和从另一世界转移过来,所以状态转移方程:dp[1][i]=max(dp[1][i-1],dp[2][i-1]-k)+dp[1][i]
只在dp[2][i-1]>=k的情况下满足,另一个世界也同理
这里注意初始化全部为-0x3f3f3f3f表示无法到达,这里不能是0!!!,0也会被视为可以到达的状态。导致后面错误多加了状态,这里只要负数足够小,那么就不会被加到正数影响状态。
最后附上代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF -0x3f3f3f3f
int dp[3][200010];
void solve() {
int n, k;
cin >> n >> k;
memset(dp,INF,sizeof(dp));
vector<int>b(n + 1);
vector<int>l(n + 1);
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++){
cin>>l[i];
}
dp[1][1]=b[1];
dp[2][1]=INF;
for(int i=2;i<=n;i++){
if(dp[2][i-1]>=k){
dp[1][i]=max(dp[1][i-1],dp[2][i-1]-k)+b[i];
}else dp[1][i]=dp[1][i-1]+b[i];
if(dp[1][i-1]>=k){
dp[2][i]=max(dp[2][i-1],dp[1][i-1]-k)+l[i];
}else dp[2][i]=dp[2][i-1]+l[i];
}
cout<<(dp[1][n]>dp[2][n]?dp[1][n]:dp[2][n]);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
return 0;
}

京公网安备 11010502036488号