题意分析

给定长度为 $n$ 的序列，两个玩家交替从序列两端取牌，第二玩家固定用贪心策略（总是取两端较大者，平局取左端），第一个玩家可采用任意策略。求在最优对抗下，第二玩家的贪心策略最坏会比第一玩家少多少分。

解题思路

定义 $f(x,y)$ 为当前玩家在子区间 $[x..y]$ 上，与对手分数差的最大值。

• 当只剩两张牌时，$f(x,x+1)=|a[x]-a[x+1]|$。

• 否则，当前玩家可先取左端 $a[x]$ 或右端 $a[y]$：

  1. 如果先取左端，则对手（贪心）会比较 $a[x+1]$ 与 $a[y]$，取较大者，剩余区间由当前玩家继续获得差值 $f(\dots)$；
  2. 如果先取右端，同理； 取两种选择中差值更大的，即

$$f(x,y)=\max\bigl( a[x]-\text{greedy\_take}(x+1,y)+f(\dots),\; a[y]-\text{greedy\_take}(x,y-1)+f(\dots) \bigr). $$

用二维数组 $dp[x][y]$ 记忆，最终答案为 $f(0,n-1)$。

---

本题代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<limits.h>
using namespace std;
const int maxn=1100;
int dp[maxn][maxn];
int a[maxn],n;
int solve(int x,int y)
{
   if(dp[x][y]!=-1)
      return dp[x][y];
   if(x+1==y)
      return dp[x][y]=abs(a[x]-a[y]);
   int sa,sb;
   if(a[x+1]>=a[y])//第一个人选左端
      sa=solve(x+2,y)+a[x]-a[x+1];
   else
      sa=solve(x+1,y-1)+a[x]-a[y];
   if(a[x]<a[y-1])//第一个人选右端
      sb=solve(x,y-2)+a[y]-a[y-1];
   else
      sb=solve(x+1,y-1)+a[y]-a[x];
   return dp[x][y]=max(sa,sb);
}
 
int main()
{
    int l=0;
    while(~scanf("%d",&n)&&n)
    {
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        memset(dp,-1,sizeof(dp));
        printf("In game %d, the greedy strategy might lose by as many as %d points.\n",++l,solve(0,n-1));
    }
    return 0;
}