题解 | #D 智乃与长短期主义者博弈#

这里一眼盯真发现是一道区间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];
}