因为数的总和一定，所以用一个人得分越高，那么另一个人的得分越低。
用$dp[i][j]$表示从$[i, j]$开始游戏，先手能够取得的最高分。
转移通过枚举取的数的个数$k$来转移。因为你希望先手得分尽量高，所以另一个人的最高得分应尽量少。
$dp[i][j] = sum[i][j] - \min \{dp[i + k][j],dp[i][j - k]\}$
但是发现计算$dp[i + k][j],dp[i][j - k]$的最小值的地方很重复，所以用一个$f[i][j]$储存前者的最优值，$g[i][j]$储存后者的最优值。
这样就将代码的时间复杂度优化到O(n2)
Code
/**
* uva
* Problem#10891
* Accepted
* Time:0ms
*/
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<sstream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
typedef bool boolean;
#define INF 0xfffffff
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
template<typename T>
inline void readInteger(T& u){
char x;
long long aFlag = ;
while(!isdigit((x = getchar())) && x != '-');
if(x == '-'){
x = getchar();
aFlag = -;
}
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
u *= aFlag;
} int n;
int *list;
int f[][];
int g[][];
int dp[][]; inline boolean init(){
readInteger(n);
if(n == ) return false;
list = new int[(const int)(n + )];
for(int i = ; i <= n; i++){
readInteger(list[i]);
}
return true;
} int *sum;
inline void getSum(){
sum = new int[(const int)(n + )];
sum[] = ;
for(int i = ; i <= n; i++)
sum[i] = sum[i - ] + list[i];
} inline void solve(){
memset(f, 0x7f, sizeof(f));
memset(g, 0x7f, sizeof(g));
for(int i = ; i <= n; i++) f[i][i] = g[i][i] = dp[i][i] = list[i];
for(int k = ; k < n; k++){
for(int i = ; i + k <= n; i++){
int j = i + k;
int m = ;
smin(m, f[i + ][j]);
smin(m, g[i][j - ]);
dp[i][j] = sum[j] - sum[i - ] - m;
f[i][j] = min(f[i + ][j], dp[i][j]);
g[i][j] = min(g[i][j - ], dp[i][j]);
}
}
printf("%d\n", dp[][n] * - sum[n]);
delete[] list;
delete[] sum;
} int main(){
while(init()){
getSum();
solve();
}
return ;
}