https://www.luogu.org/problemnew/show/P2734

是道好dp，加深了我对区间dp的理解

一开始可以有思路：f[i][j]表示区间i-j内，先手的最大得分

但是转移有困难，因为我在思考第二个人会怎么走

实际上这是没有必要的，动态规划不考虑所有步的细节，而是从前一种状态转移，至于前一种如何，并不关心

考虑到，当f[i][j]的人先手取完之后，剩下的就是第二个人，这是可以把他认为是先手

那么第一个人可能取a[i]或a[j]，那剩下的人取的就是f[i + 1][j]或者f[i][j - 1]，那么区间i-j的和减第二个人的得分就是第一个人的得分

时间:1.0h

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;inline int read(){  int ans = 0,op = 1;  char ch = getchar();  while(ch < '0' || ch > '9')    {      if(ch == '-') op = -1;      ch = getchar();    }  while(ch >= '0' && ch <= '9')    {      (ans *= 10) += ch - '0';      ch = getchar();    }  return ans * op;}const int maxn = 105;int n;int sum[maxn],a[maxn];int f[maxn][maxn];/*int dp(int i,int j){  if(j < i) return 0;  if(f[i][j]) return f[i][j];  return f[i][j] = max(sum[j] - sum[i] - dp(i + 1,j),sum[j - 1] - sum[i - 1] - dp(i,j - 1));  }*/              int main(){  n = read();  for(int i = 1;i <= n;i++)    a[i] = read(),f[i][i] = a[i];  for(int i = 1;i <= n;i++)    sum[i] = sum[i - 1] + a[i];  for(int i = n - 1;i >= 1;i--)    for(int j = i + 1;j <= n;j++)      f[i][j] = max(sum[j] - sum[i - 1] - f[i + 1][j],sum[j] - sum[i - 1] - f[i][j - 1]);  printf("%d %d",f[1][n],sum[n] - f[1][n]);}