简单DP
dp[i][j]表示i到j取到的最优值，用dp[i+1][j]或dp[i][j-1]来更新，前缀和优化一下。
输入不要记录，不然会MLE

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=1e4+5;

int n;
int a,sum[maxn],dp[maxn][maxn];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        dp[i][i]=a;
        sum[i]=sum[i-1]+a;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j+i<=n;j++){
            dp[j][j+i]=sum[i+j]-sum[j-1]-min(dp[j+1][j+i],dp[j][j+i-1]);
        }
    }
    printf("%d",dp[1][n]);
    
    
    
    return 0;
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=10005;
int f[MAXN][MAXN];
int s[MAXN];
int a[MAXN];
int n;

void init()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],s[i]=s[i-1]+a[i];
    for(int i=1;i<=n;i++)
        f[i][i]=a[i];
}

int main()
{
    init();
    for(int l=1;l<=n-1;l++)
        for(int i=1;i<=(n-l);i++)
        {
            int j=i+l;
            f[i][j]=(s[j]-s[i-1])-min(f[i+1][j],f[i][j-1]);
        }
    cout<<f[1][n]<<endl;
}
     

都是巨啊，我蒟蒻只会分类讨论4000ms+，第一次还无聊到开两个数组致MLE
```c++
#include <bits/stdc++.h>
using namespace std;

int dp[10005][10005];
int n;
int a[10005];
int dfsj(int,int);
int dfsy(int,int);

int dfsj(int i, int j)
{
if (i == j) return a[i];
if (dp[i][j] != -1) return dp[i][j];
return dp[i][j] = max(dfsy(i, j-1)+a[j], dfsy(i+1, j)+a[i]);
}

int dfsy(int i, int j)
{
if (i == j) return 0;
if (dp[i][j] != -1) return dp[i][j];
return dp[i][j] = min(dfsj(i, j-1), dfsj(i+1, j));
}

int main()
{
memset(dp,-1,sizeof dp);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
cout << dfsj(1, n) << endl;
return 0;
}

标答：
c++
#include <iostream>
using namespace std;
int n,a[10001],f[10001][10001],g[10001];
int dfs(int m,int n)
{
if(f[m][n]>0)
return f[m][n];
if(m==n)
return f[m][n]=a[m];
return f[m][n]=max(g[n-1]-g[m-1]-dfs(m,n-1)+a[n],a[m]+g[n]-g[m]-dfs(m+1,n));
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
g[i]=g[i-1]+a[i];
cout<<dfs(1,n);
return 0;
}


f[l][r]表示 取l到r的数 先手取的数之和 比 后手的 最多 多 多少
f[l][l]=a[l]
f[l][r]=(a[l]-f[l+1][r],a[r]-f[l][r-1])
ans=(f[1][n]+sum)/2

递推比记忆化搜索快很多
时间约缩短了60%

使用int足矣

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,a[10005],f[10005][10005],sum;
int main(){
scanf("%d",&n);
fo(i,1,n){
scanf("%d",&a[i]);
sum+=a[i];
}
fo(i,1,n)
f[i][i]=a[i];
fo(i,1,n-1)//i表示块的长度
fo(j,1,n-i){//j表示起点位置
f[j][i+j]=max(a[j]-f[j+1][i+j],a[i+j]-f[j][i+j-1]);
}
printf("%d\n",(sum+f[1][n])>>1);
return 0;
}