这里一眼盯真发现是一道区间dp,然后就是去写状态转移方程了。
我们定义为当前局势为
时,长期主义者可获得最大收益。
那么,当前如果是短期主义者的回合,则有:
当前如果是长期主义者的回合,则有:
那么最终答案分别为: 和
。
代码如下:
int main(){
cin>>n;
ll sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
// 长期者的收益 max( w[l] + f[l+1][r],w[r] + f[l][r-1]) 所以每次要维护这个值
// 然后由这个值去看他的操作
for(int i=1;i<=n;i++){
f[i][i]=n&1?0:a[i];
}
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
if((n+len)&1) f[l][r]=max(a[l]+f[l+1][r],a[r]+f[l][r-1]);
else f[l][r]=a[l]>=a[r]?f[l+1][r]:f[l][r-1];
}
}
cout<<sum-f[1][n]<<' '<<f[1][n];
}