2 1 23 53 3 10 100 20 2 4 3
53 105
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4597
题意：
给你两摞牌，每次可以任意一堆 的牌头或者牌尾抽牌。Alice先抽，Bob后抽，两个人都想抽到最多点数的牌。
做法：
dp[az][ay][bz][by]。 az,ay代表第一堆牌左边 和右边 分别抽到第几张了。然后在这个状态下 Bob抽到的点数。
因为dp表示的Bob的点数，所以牌堆里剩余奇数张牌的时候，是Bob抽，要取各种抽法的最大值。如果只剩偶数张牌，那么是Alice抽，要取 各种抽法中 的最小值。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <malloc.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#include <stack>
#include <queue>
#include <vector>
#include <deque>
#include <set>
#include <map>
int dp[30][30][30][30];
int a[30];
int b[30];
int dfs(int az,int ay,int bz,int by)//总数是偶数
{
if(dp[az][ay][bz][by]!=-1)
return dp[az][ay][bz][by];
int sum=ay-az+by-bz+2;
int ans;
if(sum&1)
ans=0;
else
ans=9999999;
if(sum==0)
return dp[0][0][0][0]=0;
if(az<=ay)
{
if(sum%2==1)//bob 取
{
ans=max(dfs(az+1,ay,bz,by)+a[az],ans);
ans=max(dfs(az,ay-1,bz,by)+a[ay],ans);
}
else
{
ans=min(dfs(az+1,ay,bz,by),ans);
ans=min(dfs(az,ay-1,bz,by),ans);
}
}
if(bz<=by)
{
if(sum%2==1)
{
ans=max(dfs(az,ay,bz+1,by)+b[bz],ans);
ans=max(dfs(az,ay,bz,by-1)+b[by],ans);
}
else
{
ans=min(dfs(az,ay,bz+1,by),ans);
ans=min(dfs(az,ay,bz,by-1),ans);
}
}
return dp[az][ay][bz][by]=ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
memset(dp,-1,sizeof dp);
a[0]=a[n+1]=b[0]=b[n+1]=0;
int sum=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i+1]);
sum+=a[i+1];
}
for(int i=0;i<n;i++)
{
scanf("%d",&b[i+1]);
sum+=b[i+1];
}
printf("%d\n",sum-dfs(1,n,1,n));
}
return 0;
}
原文：http://blog.csdn.net/u013532224/article/details/45605197