【P2668】斗地主【NOIP2015】

本文主要是介绍【P2668】斗地主【NOIP2015】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://www.luogu.org/problemnew/show/P2668

题目描述

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由 n 张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。

现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。

需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：

在这里插入图片描述

输入输出格式

输入格式：

第一行包含用空格隔开的2个正整数 T,n ，表示手牌的组数以及每组手牌的张数。

接下来 T 组数据，每组数据 n 行，每行一个非负整数对 a_i,b_i，表示一张牌，其中a_i表示牌的数码，b_i表示牌的花色，中间用空格隔开。特别的，我们用 1 来表示数码 A， 11 表示数码 J， 12 表示数码 Q， 13 表示数码 K；黑桃、红心、梅花、方片分别用 1−4 来表示；小王的表示方法为 0 1 ，大王的表示方法为 0 2 。

输出格式：

共 T 行，每行一个整数，表示打光第 i 组手牌的最少次数。

输入输出样例

输入样例#1：

1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1

输出样例#1：

输入样例#2：

1 17
12 3
4 3
2 3
5 4
10 2
3 3
12 2
0 1
1 3
10 1
6 2
12 1
11 3
5 2
12 4
2 2
7 2

输出样例#2：

说明

样例1说明

共有1组手牌，包含8张牌：方片7，方片8，黑桃9，方片10，黑桃J，黑桃5，方片A以及黑桃A。可以通过打单顺子（方片7，方片8，黑桃9，方片10，黑桃J），单张牌（黑桃5）以及对子牌（黑桃A以及方片A）在3次内打光。

对于不同的测试点，我们约定手牌组数T与张数n的规模如下：

在这里插入图片描述

数据保证：所有的手牌都是随机生成的。

思路

（~~弱弱的说一句俺斗地主玩的超级差QAQ~~ ）

这道题的核心解法在于搜索（外加一点点的贪心）
由题目分析可知，花色这东西是没啥用的，所以直接不管
并且容易发现，出牌的顺序对于这道题没有任何影响

因此，我们应该先把顺子打出来（这样我们可以快速+轻松+愉快的打出五张以上的牌），剩下的就用贪心，能多带牌就多带牌。
顺子的话，直接暴力，先搜三顺子，到双顺子，再单顺子（贪心），在带牌的时候从四带二开始一个个枚举，差不多就是这样。

注意

统计顺子的时候不能将大小鬼2统计进去！
四带二可以带一对，两单张，两对
注意细节！

Code

//斗地主（搜索）
#include<bits/stdc++.h>
using namespace std;
int card[20],n,T,ans;
inline int read(){int num=0;char ch;ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch<='9'&&ch>='0'){num=num*10+ch-'0';ch=getchar();}return num;
}
void init(){int a,b;memset(card,0,sizeof(card));for(int i=1;i<=n;i++){a=read(),b=read();if(a>=3&&a<=13)card[a-2]++;if(a==1)card[12]++;if(a==2)card[13]++;if(a==0)card[14]++;}ans=n;
}
inline int SP(){int cnt[5]={0},temp[18]={0},res=0;for(int i=1;i<=14;i++)cnt[card[i]]++;for(int i=1;i<=14;i++)temp[i]=card[i];if(cnt[4]&&(cnt[3]>2||cnt[2]>2)){//四带二对 for(int i=1;i<=14;i++){if(temp[i]==4){for(int j=1;j<=14;j++){if((j==i)||(temp[j]!=2))continue;if(temp[i]!=4)break;for(int k=1;k<=14;k++){if(k==i||k==j)continue;if(temp[k]==2){temp[i]-=4,temp[j]-=2,temp[k]-=2;res++;cnt[4]--;break;}}}}}}if(cnt[4]&&(cnt[3]||cnt[2]||(cnt[1]))){//四带二单 for(int i=1;i<=14;i++){if(temp[i]==4){for(int j=1;j<=14;j++){if((i==j)||temp[j]!=1)continue;if(temp[i]!=4)break;for(int k=1;k<=14;k++){if((i==k)||(j==k))continue;if(temp[k]==1){temp[i]-=4,temp[j]--,temp[k]--;res++;break;}}}}}}if(cnt[4]&&(cnt[3]||cnt[2])){//四带一对 for(int i=1;i<=14;i++){if(temp[i]==4){for(int j=1;j<=14;j++){if(j==i)continue;if(temp[j]==2){temp[i]-=4,temp[j]-=2,res++;cnt[4]--;break;}}}} }for(int i=1;i<=14;i++){//三带二、一if(temp[i]>=3){for(int j=1;j<=14;j++){if(i==j)continue;if(temp[j]==2){temp[i]-=3,temp[j]-=2,res++;break;}if(temp[j]==1){temp[i]-=3,temp[j]--,res++;break;}}}}for(int i=1;i<=14;i++){//散牌 if(temp[i]==4)temp[i]-=4,res++;else if(temp[i]==3)temp[i]-=3,res++;else if(temp[i]==2)temp[i]-=2,res++;else if(temp[i]==1)temp[i]--,res++;}return res;
}
void DFS(int deep){if(deep>=ans)return;for(int i=1;i<=14;i++){if(card[i])break;if(i==14){ans=deep;return;}}int temp=SP();if(temp+deep<ans)ans=temp+deep;int cnt[5]={0};for(int i=1;i<=14;i++)cnt[card[i]]++;if(cnt[3]>=2){//三顺子 for(int i=1;i<=10;i++){for(int l=2;l<=12;l++){for(int p=i;p<=l+i;p++){if((card[p]<3)||(p>12))break;else{if(p==l+i){for(int q=p-l;q<=p;q++)card[q]-=3;cnt[3]-=l+1; DFS(deep+1); cnt[3]+=l+1;for(int q=p-l;q<=p;q++)card[q]+=3;}}}}}}if(cnt[2]>=3){//双顺子 for(int i=1;i<=10;i++){for(int l=2;l<=12;l++){for(int p=i;p<=l+i;p++){if((card[p]<2)||(p>12))break;else{if(p==l+i){for(int q=p-l;q<=p;q++)card[q]-=2;cnt[2]-=l+1; DFS(deep+1); cnt[2]+=l+1;for(int q=p-l;q<=p;q++)card[q]+=2;}}}}}}if(cnt[1]+cnt[2]+cnt[3]>5){//单顺子 for(int i=1;i<=10;i++){for(int l=4;l<=12;l++){for(int p=i;p<=i+l;p++){if((!card[p])||(p>12))break;else{if(p==l+i){for(int q=p-l;q<=p;q++)card[q]--;DFS(deep+1);for(int q=p-l;q<=p;q++)card[q]++;}}}}}}
}
int main(){T=read(),n=read();while(T--){init();DFS(0);printf("%d\n",ans);}return 0;
}