dp一下 dp[i][j]表示到i行j列能得到的最多金币数量,那么i行j列可以从i行j-1列跟i^1行j-1列转移,注意一下转移条件就可以了,最后答案给dp[0][n],dp[1][n]取一下max就行了
void solve(){
int n,k;
cin>>n>>k;
ll c[2][n+1];
for(int i=1;i<=n;i++){
cin>>c[0][i];
}
for(int i=1;i<=n;i++){
cin>>c[1][i];
}
vector<vector<ll>> dp(2,vector<ll>(n+1,-1e18));
dp[0][1]=c[0][1];
for(int i=2;i<=n;i++){
for(int j=0;j<2;j++){
if(dp[j^1][i-1]>=k){
dp[j][i]=max(dp[j^1][i-1]+c[j][i]-k,dp[j][i]);
}
dp[j][i]=max(dp[j][i-1]+c[j][i],dp[j][i]);
}
}
cout<<max(dp[1][n],dp[0][n]);
}

京公网安备 11010502036488号