题目大意：给出n(≤500)个数，两个人轮流取数，每次可以从数列左边或者右边取一个数，直到所有的数被取完，两个人都以最优策略取数，求最后两人所得分数。
显然这种类型的博弈题，第一眼就是极大极小搜索+记忆化，但是我并不是很会极大极小搜索TAT。然后第二眼发现可以用DP写，而且显然比极大极小搜索好写啊。这一类的题有一个最普遍的做法，预处理出前缀和，然后f[i][j]表示从第i个数到第j个数先手可得到的最大得分，则有$$f[i][j]=sum[j]-sum[i-1]-min(f[i+1][j],f[i][j-1]);$$【第i个数到第j个数的和减去min(第i+1个数到第j个数先手可得到的最大得分,第i个数到第j-1个数先手可得到的最大得分)】
要注意一点，由于$$f[i][j]$$需要用到$$f[i+1][j]和f[i][j-1]$$，所以我们需要枚举的是i到j这个区间的长度，先把区间长度小的计算出来，才能计算区间长度大的，一开始就被这个坑了，果然我还是太弱了= =。。。
代码如下:
var
n,i,j,x:longint;
f:array[..,..]of longint;
sum:array[..]of longint; function min(a,b:longint):longint;
begin
if a<b then exit(a);
exit(b);
end; begin
readln(n);
for i:= to n do
begin
read(x);
sum[i]:=sum[i-]+x;//前缀和
f[i][i]:=x;
end;
for j:= to n- do//枚举区间长度
for i:= to n-j do//枚举起点
f[i][i+j]:=sum[i+j]-sum[i-]-min(f[i+][i+j],f[i][i+j-]);
writeln(f[][n],' ',sum[n]-f[][n]);//后手为sum[n]-f[][n]
end.
其实还可以省一维。
代码如下：
var
n,i,j,x:longint;
f:array[..]of longint;
sum:array[..]of longint; function min(a,b:longint):longint;
begin
if a<b then exit(a);
exit(b);
end; begin
readln(n);
for i:= to n do
begin
read(x);
sum[i]:=sum[i-]+x;
f[i]:=x;
end;
for i:= to n- do
for j:= to n-i do
f[j]:=sum[j+i]-sum[j-]-min(f[j],f[j+]);
writeln(f[],' ',sum[n]-f[]);
end.
当然，我不会极大极小搜索是因为我是蒟蒻啊。。。这道题HR神犇用的就是极大极小搜索，真是太神了%%%。
dfs(l,r)表示已在左边取了l个数，已在右边取了r个数，在剩下的数里取，最多比对手多多少分，则有$$dfs(l,r):=max(a[l+1]-dfs(l+1,r),a[n-r]-dfs(l,r+1));$$由于双方都用最优策略，所以最多比对手多多少分=max(取左边的数-对手接下来最多比你多多少分，取右边的数-对手接下来最多比你多多少分);则先手分数为（总分+先手最多比后手多多少分）div 2，而后手得分则为（总分-先手最多比后手多多少分）div 2。
代码如下：
var n,i,j,res,sum:longint;
a:array[..] of longint;
f:array[..,..] of longint;
function max(a.b:longint):longint;
begin
if a>b then exit(a);
exit(b);
end;
function dfs(l,r:longint):longint;
begin
if f[l,r]<>maxlongint then exit(f[l,r]);
if l+r=n then begin
f[l,r]:=;
exit();
end;
f[l,r]:=max(a[l+]-dfs(l+,r),a[n-r]-dfs(l,r+));
exit(f[l,r]);
end;
begin
readln(n);
sum:=;
for i:= to n do begin
read(a[i]);
inc(sum,a[i]);
end;
for i:= to n do
for j:= to n-i do
f[i,j]:=maxlongint;
res:=dfs(,);
writeln((sum+f[,]) div ,' ',(sum-f[,]) div );
end.