博弈+

博弈 codevs 3196 黄金宝藏  http://codevs.cn/problem/3196/
两个人轮流取数，每次可以从数列左边或者右边取一个数，直到所有的数被取完，两个人都[size=large]以最优策略取数，求最后两人所得分数。[/size]

引用

http://www.cnblogs.com/Sakits/p/5348629.html

方法一
预处理出前缀和，然后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个数先手可得到的最大得分)】

var
  n,i,j,x:longint;
  f:array[0..500,0..500]of longint;
  sum:array[0..500]of longint;

function min(a,b:longint):longint;
begin
  if a<b then exit(a);
  exit(b);
end;

begin
  readln(n);
  for i:=1 to n do
  begin
    read(x);
    sum[i]:=sum[i-1]+x;//前缀和
    f[i][i]:=x;
  end;
  for j:=1 to n-1 do//枚举区间长度
  for i:=1 to n-j do//枚举起点
  f[i][i+j]:=sum[i+j]-sum[i-1]-min(f[i+1][i+j],f[i][i+j-1]);
  writeln(f[1][n],' ',sum[n]-f[1][n]);//后手为sum[n]-f[1][n]
end.

方法二
极大极小搜索
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[0..1000] of longint;
    f:array[0..600,0..600] 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]:=0;
    exit(0);
  end;
  f[l,r]:=max(a[l+1]-dfs(l+1,r),a[n-r]-dfs(l,r+1));
  exit(f[l,r]);
end;
begin
  readln(n);
  sum:=0;
  for i:=1 to n do begin
    read(a[i]);
    inc(sum,a[i]);
  end;
  for i:=0 to n do
  for j:=0 to n-i do
  f[i,j]:=maxlongint;
  res:=dfs(0,0);
  writeln((sum+f[0,0]) div 2,' ',(sum-f[0,0]) div 2);
end.