HDU 4597 Play Game （記憶化搜索）

題意：有兩堆n張的卡片，每張卡片有一個得分，Alice和Bob輪流在兩堆卡片的兩端取卡片

問Alice先手，取得分數最多為多少；

#include   
#include   
#include   
#include   
#include  
#include   
#define M 50  
#define LL long long  
using namespace std;

int n;
int dp[M][M][M][M];
int x[M],y[M],sum1[M],sum2[M];
int dfs(int a,int b,int c,int d)
{
	if(dp[a][b][c][d]) return dp[a][b][c][d];
	if(a>b&&c>d) return 0;
	int ans1=0,ans2=0;
	if(a<=b)
	{
		ans1=max(x[a]+dfs(a+1,b,c,d),x[b]+dfs(a,b-1,c,d));
	}
	if(c<=d)
	{
		ans2=max(y[c]+dfs(a,b,c+1,d),y[d]+dfs(a,b,c,d-1));
	}
	return dp[a][b][c][d]=sum1[b]-sum1[a-1]+sum2[d]-sum2[c-1]-max(ans1,ans2);  

}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{   
		scanf("%d",&n);
		memset(dp,0,sizeof(dp));
		sum1[0]=0;sum2[0]=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&x[i]);
			sum1[i]=sum1[i-1]+x[i];
		}
		for(int i=1;i<=n;i++)
		{   
			scanf("%d",&y[i]);
			sum2[i]=sum2[i-1]+y[i];
		}
		printf("%d\n",sum1[n]+sum2[n]-dfs(1,n,1,n));
	}
	return 0;
}