陕西师范大学第七届程序设计竞赛网络同步赛 iko和她的糖

题目链接

考虑所有情况，求全局最优解，也就是答案。

dp[i][j]表示到达第i处选择了j次补给

#include<iostream>

#include<cstring>

using namespace std;

int dp[1234][5],a[1234],b[1234];

int main()

{

int n;

cin>>n;

for(int i=1;i<=n;i++) cin>>a[i];

for(int i=1;i<n;i++) cin>>b[i];

memset(dp,-1,sizeof(dp));

dp[1][0]=dp[0][0]=0;

b[0]=0;

for(int i=1;i<=n;i++)

{

for(int j=1;j<=3;j++)

{

if(dp[i-1][j]>=b[i-1])

dp[i][j]=max(dp[i][j],dp[i-1][j]-b[i-1]);

if(dp[i-1][j-1]>=b[i-1])

dp[i][j]=max(dp[i][j],dp[i-1][j-1]-b[i-1]+a[i]);

}

}

cout<<dp[n][3]<<endl;

return 0;

}