HDU 4597 Play Game 2013 ACM-ICPC吉林通化全国邀请赛H题

发布时间:2016-12-8 19:58:50 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 4597 Play Game 2013 ACM-ICPC吉林通化全国邀请赛H题",主要涉及到HDU 4597 Play Game 2013 ACM-ICPC吉林通化全国邀请赛H题方面的内容,对于HDU 4597 Play Game 2013 ACM-ICPC吉林通化全国邀请赛H题感兴趣的同学可以参考一下。

九野的博客,转载请注明出处:  http://blog.csdn.net/acmmmm/article/details/10833941 题意:给定T个测试数据,下面有2副牌,每副n张,每张都有一个分值 问:2个人轮流取牌,每次取一张(从任意一副的牌顶或牌底取),先手可获得的最大分值   开始往博弈想了,这题是记忆化搜索 #include<stdio.h> #include<algorithm> #include<iostream> #include<set> #include<math.h> #include<string.h> #define N 25 using namespace std; int card1[N],card2[N],sum1[N],sum2[N]; int dp[N][N][N][N]; // dp[below1][top1][below2][top2] 表示当2个牌堆是这样时可以取得的最大值 inline int Max(int a,int b){return a>b?a:b;} int dfs(int below1,int top1,int below2,int top2){//返回 牌堆是这样时能取得的最大值 if(dp[below1][top1][below2][top2]!=-1)return dp[below1][top1][below2][top2]; if(below1>top1 && below2>top2) {//牌堆取完 dp[below1][top1][below2][top2]=0; return 0; } int sum=0,ans=0;//sum表示剩下牌堆的总分 if(below1<=top1)sum+= sum1[top1]-sum1[below1-1]; if(below2<=top2)sum+= sum2[top2]-sum2[below2-1]; if(below1<=top1){ ans=Max(ans,sum-dfs(below1+1,top1,below2,top2)); ans=Max(ans,sum-dfs(below1,top1-1,below2,top2)); } if(below2<=top2){ ans=Max(ans,sum-dfs(below1,top1,below2+1,top2)); ans=Max(ans,sum-dfs(below1,top1,below2,top2-1)); } return dp[below1][top1][below2][top2]=ans; } int main(){ int T,i,n;scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&card1[i]); for(i=1;i<=n;i++)scanf("%d",&card2[i]); sum1[0]=sum2[0]=0; for(i=1;i<=n;i++) sum1[i]=sum1[i-1]+card1[i],sum2[i]=sum2[i-1]+card2[i]; memset(dp,-1,sizeof(dp)); printf("%d\n",dfs(1,n,1,n)); } return 0; }  

上一篇:android项目嫁接过程经验总结
下一篇:职业规划

相关文章

相关评论