题解：洛谷 P2540 [NOIP 2015 提高组] 斗地主 加强版

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2540 [NOIP 2015 提高组] 斗地主 加强版 - 洛谷【题目描述】牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A AA到K KK加上大小王的共54 5454张牌来进行的扑克牌游戏。在斗地主中牌的大小关系根据牌的数码表示如下3 4 5 6 7 8 9 10 J Q K A 2 小王 大王 345678910JQKA2\text{小王}\text{大王}345678910JQKA2小王大王而花色并不对牌的大小产生影响。每一局游戏中一副手牌由n nn张牌组成。游戏者每次可以根据规定的牌型进行出牌首先打光自己的手牌一方取得游戏的胜利。现在牛牛只想知道对于自己的若干组手牌分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。需要注意的是本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下在此题中认为两个王不能组成对子牌。【输入】第一行包含用空格隔开的2 22个正整数T , n T,nT,n表示手牌的组数以及每组手牌的张数。接下来T TT组数据每组数据n nn行每行一个非负整数对a i , b i a_i,b_iai​,bi​表示一张牌其中a i a_iai​表示牌的数码b i b_ibi​表示牌的花色中间用空格隔开。特别的我们用1 11来表示数码A AA11 1111表示数码J JJ12 1212表示数码Q QQ13 1313表示数码K KK黑桃、红心、梅花、方片分别用1 − 4 1-41−4来表示小王的表示方法为0 1大王的表示方法为0 2。【输出】共T TT行每行一个整数表示打光第i ii手牌的最少次数。【输入样例】1 8 7 4 8 4 9 1 10 4 11 1 5 1 1 4 1 1【输出样例】3【算法标签】#省选# #IDA*#【代码详解】#includebits/stdc.husingnamespacestd;constintN30;// 牌面值种类数量intt,n;// t: 测试用例数量, n: 每手牌的数量intf[N][N][N][N];// 记忆化数组f[s][t][j][z]表示在给定牌型下的最小出牌次数intwasd[4]{0,5,3,2};// 不同牌型的最小连续长度单顺5张双顺3对飞机2个三张inta[N];// 统计每种牌的数量a[i]表示牌面值为i的牌有多少张intb[N];// 牌型转换数组b[1]单牌数b[2]对子数b[3]三张数b[4]炸弹数// 辅助函数返回两个整数中的较小值intcmp(inta,intb){returnab?a:b;}// 深度优先搜索函数计算在给定基本牌型下的最小出牌次数// 参数说明// s: 单牌的数量// t: 对子的数量// j: 三张的数量// z: 炸弹的数量intdfs(ints,intt,intj,intz){// 如果这个状态已经计算过直接返回结果if(~f[s][t][j][z]){returnf[s][t][j][z];}intans1e9;// 初始化为一个很大的数// 策略1拆分对子为两个单牌if(t){anscmp(ans,dfs(s2,t-1,j,z));}// 策略2拆分三张为一个对子和一个单牌if(j){anscmp(ans,dfs(s1,t1,j-1,z));}// 策略3拆分炸弹为一个三张和一个单牌if(z){anscmp(ans,dfs(s1,t,j1,z-1));}// 策略4拆分炸弹为两个对子if(z){anscmp(ans,dfs(s,t2,j,z-1));}// 策略5三带一用三张带一个单牌if(js){anscmp(ans,dfs(s-1,t,j-1,z)1);}// 策略6三带二用三张带一个对子if(jt){anscmp(ans,dfs(s,t-1,j-1,z)1);}// 策略7四带二单用炸弹带两个单牌if(zs1){anscmp(ans,dfs(s-2,t,j,z-1)1);}// 策略8四带二对用炸弹带两个对子if(zt1){anscmp(ans,dfs(s,t-2,j,z-1)1);}// 策略9一手出完所有牌每个单牌、对子、三张、炸弹都单独出returnf[s][t][j][z]cmp(ans,stjz);}// 处理顺子、连对、飞机等特殊牌型// 参数说明step - 当前已经出的次数intchupai(intstep){intans1e9;// 初始化为一个很大的数inttot;// 用于统计连续牌的数量// 处理三种特殊牌型k1单顺k2双顺k3飞机for(intk1;k3;k){// 从3开始遍历因为顺子从3开始3,4,5,...for(inti3;i14;i){tot0;// 统计从i开始最多有多少张连续的牌for(intji;j14;j){if(a[j]k)// 如果当前牌有至少k张{tot;}else{break;// 不连续了停止统计}}// 枚举所有可能的顺子长度for(intjiwasd[k]-1;jitot-1;j){// 移除这个顺子for(intli;lj;l){a[l]-k;}// 递归处理剩下的牌anscmp(ans,chupai(step1));// 恢复这个顺子进行回溯for(intli;lj;l){a[l]k;}}}}// 统计剩余的牌型b[1]b[2]b[3]b[4]0;// 初始化牌型数组for(inti2;i14;i)// 从2到A14统计{b[a[i]];// 根据牌的数量统计牌型}// 处理大小王if(a[0]2)// 如果有两张王大小王{// 可以当作一对王炸anscmp(ans,step1dfs(b[1],b[2],b[3],b[4]));}// 将王当作单牌处理b[1]a[0];anscmp(ans,stepdfs(b[1],b[2],b[3],b[4]));returnans;}intmain(){// 输入测试用例数量和每手牌的数量cintn;// 初始化记忆化数组memset(f,-1,sizeof(f));f[0][0][0][0]0;// 基础情况没有牌需要0次出牌// 处理每个测试用例while(t--){intu,v;// u: 牌面值, v: 花色memset(a,0,sizeof(a));// 清空牌数统计// 输入n张牌for(inti1;in;i){cinuv;a[u];// 统计该牌面值的数量}// 将A1映射到14便于处理顺子a[14]a[1];// 计算最少出牌次数并输出coutchupai(0)endl;}return0;}【运行结果】1 8 7 4 8 4 9 1 10 4 11 1 5 1 1 4 1 1 3