题意：
给一列数a[1...n],A和B轮流从其中剩余两端取一个数，B只能取两端数最大的，取完后比较谁的和大，问A最多可以比B多多少。
分析：
区间动态规划，状态dp[i][j]:A能从第i到第j个数中获得的最大和。转移：根据当前区间长度分奇偶考虑，详见代码。
代码：
//poj 2738
//sepNINE
#include <iostream>
using namespace std;
const int maxN=1024;
int a[maxN];
int dp[maxN][maxN];int main()
{int i,j,k,n,sum,cases=0;while(scanf("%d",&n)==1&&n){for(i=1;i<=n;++i)scanf("%d",&a[i]);memset(dp,0,sizeof(dp));sum=0;for(i=1;i<n;++i)dp[i][i+1]=max(a[i],a[i+1]);for(i=1;i<=n;++i)sum+=a[i]; for(k=2;k<n;++k)for(i=1;i+k<=n;++i){j=i+k;if((j-i+1)%2==0) dp[i][j]=max(dp[i+1][j]+a[i],dp[i][j-1]+a[j]);else{if(a[i]>=a[j])dp[i][j]=dp[i+1][j];elsedp[i][j]=dp[i][j-1]; }}printf("In game %d, the greedy strategy might lose by as many as %d points.\n",++cases,2*dp[1][n]-sum);}return 0;
}