首页 > 代码库 > HDU 4597
HDU 4597
题目大意:
两人轮流从两堆牌从抽取最顶端或者最底部的牌,得到的分数加到自己身上,问先拿牌的最多能得多少分
记忆化搜索,2堆牌的底和顶,有四种方法,根据四种方法来找到最优解
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 int dp[22][22][22][22],p[22],q[22]; 6 int dfs(int a,int b,int c,int d,int sum) 7 { 8 int maxn=0; 9 if(a>b&&c>d) return 0;10 if(dp[a][b][c][d]) return dp[a][b][c][d];11 if(a<=b){12 maxn=max(maxn,sum-dfs(a+1,b,c,d,sum-p[a]));13 maxn=max(maxn,sum-dfs(a,b-1,c,d,sum-p[b]));14 }15 if(c<=d){16 maxn=max(maxn,sum-dfs(a,b,c+1,d,sum-q[c]));17 maxn=max(maxn,sum-dfs(a,b,c,d-1,sum-q[d]));18 }19 dp[a][b][c][d]=maxn;20 return maxn;21 }22 int main()23 {24 int T,n,sum;25 scanf("%d",&T);26 while(T--){27 sum=0;28 scanf("%d",&n);29 for(int i=1;i<=n;i++){30 scanf("%d",&p[i]);31 sum+=p[i];32 }33 for(int i=1;i<=n;i++){34 scanf("%d",&q[i]);35 sum+=q[i];36 }37 memset(dp,0,sizeof(dp));38 int ans=dfs(1,n,1,n,sum);39 printf("%d\n",ans);40 }41 return 0;42 }
HDU 4597
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。