学步园

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4597

题目意思：

给两堆数，A和B两个人比赛，每次每人只能拿每堆的第一个或最后一个数，两人均表现最佳，问A开始，他能拿到的数和最大是多少。

解题思路：

对抗搜索，或dp.

一拿到这道题就知道是记忆化搜索，但状态转移，一直没弄很清楚，卡了很久，最后由于水题看错了，搞了几个小时。。。。最后就没最后了。。。

开始dp一直搞成5维的，最后一维表示谁先开始。但是这样转移的时候不能直接加进去，因为后面是另外一个人的。

最后听了峰峰的想法，因为只有两个人，dfs的时候维护一个参数表示剩余的总和sum，用sum减去另外一个人的最大就是当前自己得到的！ORZ。

这类dp做的比较少。以后多做些。

dp[a][b][c][d]表示从第一推的a~b,第二维的c~d选能达到的最大值。

PS：状态转移不一定非得+，--减也行的。

代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;


//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);

#define Maxn 22
int dp[Maxn][Maxn][Maxn][Maxn];
int aa[Maxn],bb[Maxn],n;

int dfs(int a,int b,int c,int d,int sum)
{
   if(dp[a][b][c][d]!=-1)
      return dp[a][b][c][d];
   if(a>b&&c>d) //已经结束了
   {
      dp[a][b][c][d]=0;
      return 0;
   }
   int res=0;
   if(a<=b)
   {
      res=max(res,sum-dfs(a+1,b,c,d,sum-aa[a]));//当前人选a
      res=max(res,sum-dfs(a,b-1,c,d,sum-aa[b]));//当前人选b
   }
   if(c<=d)
   {
      res=max(res,sum-dfs(a,b,c+1,d,sum-bb[c]));//当前人选c
      res=max(res,sum-dfs(a,b,c,d-1,sum-bb[d]));//当前人选d
   }
   dp[a][b][c][d]=res;
   return res;
}

int main()
{
   int t;

   scanf("%d",&t);
   while(t--)
   {
      scanf("%d",&n);
      int sum=0;
      for(int i=1;i<=n;i++)
         scanf("%d",&aa[i]),sum+=aa[i];
      for(int i=1;i<=n;i++)
         scanf("%d",&bb[i]),sum+=bb[i];
      memset(dp,-1,sizeof(dp)); //初始化
      dfs(1,n,1,n,sum);
      printf("%d\n",dp[1][n][1][n]);
   }
   return 0;
}