考虑所有情况,求全局最优解,也就是答案。
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;
}