题解 P2668 【斗地主】
钱逸凡
2018-07-12 12:49:14
~~虽然本题是搜索，却感觉和做模拟差不多，情况很多，代码很长，打起来很烦。~~
### 首先要明确：先打顺子和四带二和三带一，最后打单牌
至于那个三连对，其实是没有用的，因为如果我们有三张牌是一样的，我们可以用来打三带一，打三连对实在是太浪费了。
### 其次：顺子并不是越长越好
为什么呢？
~~打过斗地主的可以跳过解说直接看代码~~
在我们打顺子时可能会拆散本可以打三带一和四带二的牌，导致出了更多次牌。
举个例子：3 ，4 ，5， 6， 7， 8， 9， 10， 10， 10，A（1）
如果我们打的顺子是3，4，5，6，7，8，9，10，接下来还要出两次：10，10（对子）和A。一共三次。
但如果我们的顺子是3，4，5，6，7，8，9，接下来只要出一次：10，10，10，A（三带一）。一共两次。
小细节，1(A)可以接在13后面，但是2不可以接在1后面，也不可以接在3前面。
综上所述，得出代码：
```
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int T,n,c[14],ans;
inline int Read(){
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
inline int min(int a,int b){
return a<b?a:b;
}
void init(){
register int i;
for(i=0;i<=13;i++)c[i]=0;
int a,b;
for(i=1;i<=n;i++){
a=Read(),b=Read();
c[a]++;//花色不重要
}
ans=14;
}
inline int four(){
for(int i=0;i<=13;i++){
if(c[i]==4)return i;
}
return -1;
}//是否有四张牌相同
inline int three(){
for(int i=0;i<=13;i++){
if(c[i]>=3)return i;
}
return -1;
}//是否有三张牌相同
inline bool shun(int i){
if(c[i]>=1&&
c[i+1]>=1&&
c[i+2]>=1&&
c[i+3]>=1&&
c[(i+3)%13+1]>=1)return 1;
return 0;
}//是否有顺子
inline bool dshun(int i){
if(c[i]>=2&&
c[i+1]>=2&&
c[(i+1)%13+1]>=2)return 1;
return 0;
}//是否有连对
void dfs(int deep,int leave){//打了几次，还剩几张
if(deep>=ans)return;
if(leave==0){
ans=deep;
return;
}
int k,kk,i;
//打顺子
for(i=3;i<=10;i++){
if(shun(i)){
k=i;
kk=k;
while(c[k]>=1&&k!=2){
c[k]--;
k++;
if(k-kk>=5)dfs(deep+1,leave-k+kk);//顺子并不是越长越好
if(k==14)k=1;
}//把顺子打出
if(k==1)k=14;
if(k==2)k=15;
dfs(deep+1,leave-k+kk);
if(k==15)c[1]++,k--;
k--;
for(;kk<=k;kk++)c[kk]++;//回溯
}
}
//打连对
for(i=3;i<=12;i++){
if(dshun(i)){
k=i;
kk=k;
while(c[k]>=2&&k!=2){
c[k]-=2;
k++;
if(k-kk>=3)dfs(deep+1,leave-2*k+2*kk);//同样，连对也不是越长越好
if(k==14)k=1;
}//把连对打出
if(k==1)k=14;
if(k==2)k=15;
dfs(deep+1,leave-2*k+2*kk);
if(k==15)c[1]+=2,k--;
k--;
for(;kk<=k;kk++)c[kk]+=2;//回溯
}
}
//打4带2
k=four();
if(k!=-1){
c[k]-=4;
for(int i=0;i<=13;i++){
if(c[i]==0)continue;
for(int j=0;j<=13;j++){
if(c[j]==0)continue;
if(j==i)continue;
if(c[i]>=2&&c[j]>=2){
c[i]-=2;
c[j]-=2;
dfs(deep+1,leave-8);
c[i]+=2;
c[j]+=2;
}//四带两对
if(c[i]>=1&&c[j]>=1){
c[i]-=1;
c[j]-=1;
dfs(deep+1,leave-6);
c[i]++;
c[j]++;
}//四带二
}
}
dfs(deep+1,leave-4);//打炸弹
c[k]+=4;
}
//打三带一(对)
k=three();
if(k!=-1){
c[k]-=3;
for(int i=0;i<=13;i++){
if(c[i]>=1){
c[i]--;
dfs(deep+1,leave-4);
c[i]++;
}//三带一
if(c[i]>=2){
c[i]-=2;
dfs(deep+1,leave-5);
c[i]+=2;
}//三带一对
}
dfs(deep+1,leave-3);//打三张单牌
c[k]+=3;
}
////剩下的全部打单牌和对子
int s=0;
for(int i=0;i<=13;i++){
if(c[i]>=1){
s++;
}
}
dfs(deep+s,0);
}
int main(){
T=Read();n=Read();
while(T--){
init();
dfs(0,n);
printf("%d\n",ans);
}
return 0;
}
```