P2668 斗地主 题解by Luan
Luan_233
2018-05-22 16:41:55
## Solution
### 这是我的处女作题解，有什么不当之处还望大家指出。
+ 相信这道题的解法许多斗地主大神兼OI巨佬也已经指出了，核心就在于暴力地去搜顺子，每搜完一层以后就贪心地出散牌。
+ 无论怎样来说，搜顺子有利于我们快速而轻松的打出5张甚至以上的牌，其余的东西，就留到最后慢慢打出就好了。
+ NOIP的搜索题以搜索为辅，核心在于模拟（几乎全是模拟）。所以说: **细节很重要！！！**
+ 最好把每一种打牌的方式分拆开来，按照贪心的顺序自上至下排列，搜索时只搜三种顺子，万万不可将打散牌也放进搜索里去（就是这样我连样例二都出不来。。）。
+ 我的做法是每搜新的一层时，统计牌张数的数目，这样有利于减少枚举量（细节见dfs主程序以及打散牌的函数）。
+ 在枚举顺子时，一定不可把2、小王、大王统计进去，但是在打散牌时，小王、大王当做一对来出，当做单牌或者与3张4张一起打出（虽说斗地主里王往往都在最后出，但你在这里是没有对手的）。
+ 四带二不仅可以带两张单牌，带一对牌或带两对牌都是可以的！
** _有了这些细节，做这道题还有什么好怕的呢？_ **
## Code
```
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int t,n,card[15],c,d,ans;
inline void init(){
memset(card,0,sizeof(card));
for(int i=1;i<=n;i++){
scanf("%d%d",&d,&c);
if((d>=3)&&(d<=13)) card[d-2]++;
if(d==0) card[14]++;
if(d==1) card[12]++;
if(d==2) card[13]++;
}
ans=n;
}
inline int sanpai(){
int cnt[5],temp[14],ret=0;
memset(cnt,0,sizeof(cnt));
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[2]>2||cnt[3]>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==j)||(k==i)) continue;
if(temp[k]==2){
temp[i]-=4; temp[j]-=2; temp[k]-=2;
cnt[4]--; ret++; break;
}
}
}
}
}
}//四带两对
if(cnt[4]&&(cnt[2]||cnt[3]||(cnt[1]))){
for(int i=1;i<=14;i++){
if(temp[i]==4){
for(int j=1;j<=14;j++){
if((j==i)||(temp[j]!=1)) continue;
if(temp[i]!=4) break;
for(int k=1;k<=14;k++){
if((k==j)||(k==i)) continue;
if(temp[k]==1){
temp[i]-=4; temp[j]--; temp[k]--;
ret++; break;
}
}
}
}
}
}//四带二（不重牌）
if(cnt[4]&&(cnt[2]||cnt[3])){
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; ret++;
temp[j]-=2; cnt[4]--;
break;
}
}
}
}
}//四带一对
for(int i=1;i<=14;i++){
if(temp[i]>=3){
for(int j=1;j<=14;j++){
if(j==i) continue;
if(temp[j]==2){
temp[i]-=3; temp[j]-=2; ret++;
break;
}
if(temp[j]==1){
temp[i]-=3; temp[j]--; ret++;
break;
}
}
}
}//三带二&&三带一
for(int i=1;i<=14;i++){
if(temp[i]==4) temp[i]-=4,ret++;
else if(temp[i]==3) temp[i]-=3,ret++;
else if(temp[i]==2) temp[i]-=2,ret++;
else if(temp[i]) temp[i]--,ret++;
}//散牌
return ret;
}
inline 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=sanpai();
if(temp+deep<ans) ans=temp+deep;
int cnt[5];
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=14;i++) cnt[card[i]]++;
if(cnt[3]>=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]<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(){
scanf("%d%d",&t,&n);
while(t--){
init();
dfs(0);
printf("%d\n",ans);
}
return 0;
}
```
+ 非常感谢讨论区里的hack数据，我感到十分抱歉。但是上半部分的码仅仅针对于NOIP原题数据，不考虑拆牌组牌情况，若要考虑真正的拆牌情况，可以移步增强版。（可以吐槽我的码非常的丑）。
+ 对于hack数据，顺子依然要爆搜，但原有的贪心换用DP对其进行优化。对应状态就是牌数为多少的牌有多少种，再套上一个双王的数目（可以没有），打完这些牌所需的最小步数。考虑拆牌的情况，四张拆一张与三张，或是两个两张，或是两张加一对，三张拆成一张加一对，或是三张单牌。套在记搜内直接讨论即可。对牌和单牌直接出就好。下面奉上我斗地主增强版的代码。欢迎各位吐槽。
## Code
```
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 1061109567
#define Re register
using namespace std;
int t,n,f[25][25][25][25][5],cnt[5],card[25],num,ans;
inline int dfs2(int on,int tw,int th,int fl,int w){
if(f[on][tw][th][fl][w]<INF){
return f[on][tw][th][fl][w];
}
f[on][tw][th][fl][w]=on+tw+th+fl+w;
int &now=f[on][tw][th][fl][w];
if(w==2) now=min(now,dfs2(on,tw,th,fl,0)+1);
if(fl){
if(tw>=2) now=min(now,dfs2(on,tw-2,th,fl-1,w)+1);
//直接四带二对
if(tw) now=min(now,dfs2(on,tw-1,th,fl-1,w)+1);
//四带两张一样的
if(w==2) now=min(now,dfs2(on,tw,th,fl-1,0)+1);
//王炸组四带二张
if(w&&on) now=min(now,dfs2(on-1,tw,th,fl-1,w-1)+1);
//单王加单牌组四带二
if(on>=2) now=min(now,dfs2(on-2,tw,th,fl-1,w)+1);
//直接四带二张
now=min(now,dfs2(on+1,tw,th+1,fl-1,w));
//拆成三与一
now=min(now,dfs2(on,tw+2,th,fl-1,w));
//拆成两对
now=min(now,dfs2(on+2,tw+1,th,fl-1,w));
//拆成一对加两张
}
if(th){
if(tw) now=min(now,dfs2(on,tw-1,th-1,fl,w)+1);
//直接三带二
if(w) now=min(now,dfs2(on,tw,th-1,fl,w-1)+1);
//三带一王
if(on) now=min(now,dfs2(on-1,tw,th-1,fl,w)+1);
//三带一单
now=min(now,dfs2(on+1,tw+1,th-1,fl,w));
//拆牌成一单一对
now=min(now,dfs2(on+3,tw,th-1,fl,w));
//拆牌成三张单
}
return f[on][tw][th][fl][w];
}
inline int get(){
memset(cnt,0,sizeof(cnt));
for(Re int i=1;i<=13;i++) cnt[card[i]]++;
return dfs2(cnt[1],cnt[2],cnt[3],cnt[4],card[14]);
}
inline void dfs1(int step){
ans=min(ans,step+get());
bool flag;
for(Re int i=1;i<=11;i++){
for(Re int j=2;j<=12;j++){
if(i+j-1>12) break;
flag=true;
for(Re int k=0;k<=j-1;k++){
if(card[i+k]<3) flag=false;
}
if(!flag) break;
for(Re int k=0;k<=j-1;k++) card[i+k]-=3;
dfs1(step+1);
for(Re int k=0;k<=j-1;k++) card[i+k]+=3;
}
}
for(Re int i=1;i<=10;i++){
for(Re int j=3;j<=12;j++){
if(i+j-1>12) break;
flag=true;
for(Re int k=0;k<=j-1;k++){
if(card[i+k]<2) flag=false;
}
if(!flag) break;
for(Re int k=0;k<=j-1;k++) card[i+k]-=2;
dfs1(step+1);
for(Re int k=0;k<=j-1;k++) card[i+k]+=2;
}
}
for(Re int i=1;i<=8;i++){
for(Re int j=5;j<=12;j++){
if(i+j-1>12) break;
flag=true;
for(Re int k=0;k<=j-1;k++){
if(!card[i+k]) flag=false;
}
if(!flag) break;
for(Re int k=0;k<=j-1;k++) card[i+k]-=1;
dfs1(step+1);
for(Re int k=0;k<=j-1;k++) card[i+k]+=1;
}
}
}
inline void solve(){
memset(card,0,sizeof(card));
for(int i=1;i<=n;i++){
int type,col;
cin>>type>>col;
if(type==0) type=14;
else if(type==1||type==2) type+=11;
else if(type>=3&&type<=13) type-=2;
card[type]++;
}
num=0,ans=n;
dfs1(0);
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
memset(f,63,sizeof(f));
cin>>t>>n;
for(int i=1;i<=t;i++) solve();
return 0;
}
```