[dp] Alice和Bob玩纸牌游戏。有2叠纸牌，每一叠的纸牌数量为n，并且每张纸牌都有自己的分数。轮流抽卡，求Alice所能拿到的最大分数（四维区间dp）

本文主要是介绍[dp] Alice和Bob玩纸牌游戏。有2叠纸牌，每一叠的纸牌数量为n，并且每张纸牌都有自己的分数。轮流抽卡，求Alice所能拿到的最大分数（四维区间dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

做题思路：动态规划学习路线与笔记 | 动态规划习题集
[题目来源] 2019福州大学863数据结构与程序设计真题11题：这题求的是A取的最大（那B取的要最小）
[相似题目] HDU4597 Play Game：这题求的是A、B两人都取最高，A先手取的最大得分

【题目】Alice和Bob是两个算法大神，他们玩纸牌游戏。有2叠纸牌，每一叠的纸牌数量为n，并且每张纸牌都有自己的分数。他们轮流从任一堆中拿起顶部或底部的卡片，该卡片的分数将被添加到他的总分中，并且获得该纸牌的分数。请设计一个算法，求出Alice所能拿到的最大分数（Alice先拿）

【测试数据】

【纸牌1】13、5
【纸牌2】2、10

在这里插入图片描述

代码

#include<stdio.h>
#include<string.h>
#define max(a,b) ((a)<(b)?(b):(a))
#define min(a,b) ((a)<(b)?(a):(b))
#define INF 0x7f7f7f7f//测试数据
#define N 2	
int a[N+1] = {0, 13, 5};
int b[N+1] = {0, 2, 10};int dp[N+1][N+1][N+1][N+1]; //存到1-N的位置
/* dp[al][ar][bl][br]：实际上这个数组内存放了两个人的得分（记先手的人为A、后手的人为B）
1.	剩下的牌数num=ar-al+br-bl
2.	if num%2==0 --> dp存的是A的得分 --> 依据题目意思，要求的是A的最大值，那么dp内存的A得分的最大值else num%2==1 --> dp存的是B的得分 --> 依据题目意思，要求B取最小值，即dp内存的是B得分的最小值
*/int dp_rec(int al, int ar, int bl, int br, int sum) { //sum为a[al-ar]、b[bl-br]的和int ans;if (dp[al][ar][bl][br]!=0) //有历史记录，不用再次计算return dp[al][ar][bl][br];if (al>ar && bl>br) //没牌了return 0;if ( (ar-al+br-bl)%2==0 ) { //剩下的牌为偶数张-->现在轮到先手的那个人抽卡，即A// [错误思想] 拿当前四个中最大的那个-->那是属于贪心，是错误的！鼠目寸光，不一定成立// [正确做法] 那怎么办？先拿，拿了之后，看看分数是不是最大！ans = 0;if (al<=ar) { //a堆还有牌ans = max(ans, sum-dp_rec(al+1, ar, bl, br, sum-a[al]) );// [问题] 选手A选了a[al]的牌，怎么看A得分是不是最大？// [情况] A选了a[al]的牌 --> 那么剩下的牌为a[a1+1 - ar]、b[bl - br]// [答] 此时，A抽完轮到B抽 --> dp_rec(al+1, ar, bl, br, sum-a[a1]) --> 这个值实际为B的得分// [故] sum-B的得分即是A的得分ans = max(ans, sum-dp_rec(al, ar-1, bl, br, sum-a[ar]) );}if (bl<=br) { //b堆还有牌ans = max(ans, sum-dp_rec(al, ar, bl+1, br, sum-b[bl]) );ans = max(ans, sum-dp_rec(al, ar, bl, br-1, sum-b[br]) );}} else { //剩下的牌为奇数张-->现在轮到后手的那个人抽卡，即B// [正确做法] 先拿，拿了之后，看看分数是不是最小！ans = INF;if (ar>=al) {ans = min(ans, sum-dp_rec(al+1, ar, bl, br, sum-a[al]) );ans = min(ans, sum-dp_rec(al, ar-1, bl, br, sum-a[ar]) );}if (br>=bl) {ans = min(ans, sum-dp_rec(al, ar, bl+1, br, sum-b[bl]) );ans = min(ans, sum-dp_rec(al, ar, bl, br-1, sum-b[br]) );}}printf("dp[%d][%d][%d][%d]=%d\n", al, ar, bl, br, ans);return dp[al][ar][bl][br]=ans;
}int main() {int ret,i;int sum;memset(dp, 0, sizeof(dp)); //默认为0分// 获得所有牌的总分sum = 0;for (i=1; i<N+1; ++i) {sum += a[i];sum += b[i];}printf("牌的总分:%d\n", sum);// 计算a[1-N]、b[1-N]中，先手的选手的最大得分ret = dp_rec(1, N, 1, N, sum);printf("A同学最高得分：%d\n", ret);return 0;
}