f[i][j][0]表示轮到player1选[i,j]这段的最大值；
f[i][j][1]表示轮到player2选[i,j]这段的最大值；
然后就是按照题目直接模拟~



#include<cstdio>
#include<cstring>
#include<vector>
#include<string>
#include<sstream>
#include<iostream>
#include<algorithm>
#define maxn 1050
#define inf -10500
using namespace std;
int f[maxn][maxn][2];
int n,icase=0;
vector<int> a;
bool init()
{
	a.clear();
	scanf("%d",&n);
	while (n--) 
	{
		int x;
		scanf("%d",&x);
		a.push_back(x);
	}
	return a.size();
}
int dfs(int p,int q,int x)
{
	if (f[p][q][x]>inf) return f[p][q][x];
	if (x==0)
	{
		f[p][q][x]=max(dfs(p,q-1,1)+a[q],a[p]+dfs(p+1,q,1));
	} else
	{
		f[p][q][x]=(a[p]>=a[q]?dfs(p+1,q,0)-a[p]:dfs(p,q-1,0)-a[q]);
	}
	return f[p][q][x];
}
void solve()
{
	memset(f,0x88,sizeof(f));
	for (int i=0;i<a.size();i++) f[i][i][0]=a[i],f[i][i][1]=-a[i];
	printf("In game %d, the greedy strategy might lose by as many as %d points.\n",++icase,dfs(0,a.size()-1,0));
}
int main()
{
	while (init()) solve();
	return 0;
}


默默地补一句：我的是47MS，可能是POJ宽容大量给我水过去，如有什么错误之处欢迎指出~