HDU 4597 Play Game (对抗搜索)
题意: 现在有两堆卡牌，每堆都为N张，每张卡牌有一定的分数，有A，B两个人，他们能从这两堆中的顶部或者底部抽出一张牌，并且拥有该分数，问当A先手时，他能获得的最大分数。
用dp【t1】【d1】【t2】【d2】表示在剩下的卡牌中（第一堆为t1--d1,第二堆为t2--d2），即将抽取牌的人能获得的最多分数。
怎么转移呢？ 假设游戏当前所剩卡牌分数为cur， 则当前能获得的最大分数，为cur - 下个人能获得的最大分数。
#include <iostream>#include <algorithm>#include <cmath>#include<functional>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <vector>#include <set>#include <queue>#include <stack>#include <climits>//形如INT_MAX一类的#define MAX 100005#define INF 0x7FFFFFFF#define REP(i,s,t) for(int i=(s);i<=(t);++i)#define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define mp(a,b) make_pair(a,b)#define L(x) x<<1#define R(x) x<<1|1# define eps 1e-5using namespace std;int va1[22],va2[22];int dp[22][22][22][22];int n,sum;int dfs(int t1,int d1,int t2,int d2,int cur) { if(t1 > d1 && t2 > d2) return dp[t1][d1][t2][d2] = 0; if(dp[t1][d1][t2][d2] != 0) return dp[t1][d1][t2][d2]; int cmp = 0; if(t1 <= d1) { cmp = max(cmp,cur - dfs(t1+1,d1,t2,d2,cur - va1[t1])); cmp = max(cmp,cur - dfs(t1,d1-1,t2,d2,cur - va1[d1])); } if(t2 <= d2) { cmp = max(cmp,cur - dfs(t1,d1,t2+1,d2,cur - va2[t2])); cmp = max(cmp,cur - dfs(t1,d1,t2,d2-1,cur - va2[d2])); } return dp[t1][d1][t2][d2] = cmp;}int main() { int T; cin >> T; while(T--) { scanf("%d",&n); sum = 0; for(int i=1; i<=n; i++) { scanf("%d",&va1[i]); sum += va1[i]; } for(int i=1; i<=n; i++) { scanf("%d",&va2[i]); sum += va2[i]; } memset(dp,0,sizeof(dp)); printf("%d\n",dfs(1,n,1,n,sum)); } return 0;}