NOIP2015 Day1 T3 斗地主

许多时候,我们可以把生活中遇到的棋牌游戏用算法的知识解决。我们可能需要最优打法,或者计算当前的胜率,或者通过搜索来获取需要的信息。这一类问题我们叫它棋牌类搜索题。
这篇文章以NOIP2015 Day1 T3 斗地主为例,讲述了一种棋牌类搜索题的思路。

题目意思就是说给你一副扑克牌手牌,按照题目中的规则你可以出单张、对子、带牌、顺子等牌型,问你最少需要几次可以把牌出完。

这题显然是一道搜索题,对于棋牌类的搜索题,状态复杂,搜索深度低,我们最好使用深搜。我们明确一下深搜的一般套路就是,首先判断目标状态,然后剪枝,下面遍历下一层。

我们先把题目中的牌型归一下类。首先是顺子型,和牌的数字有关,数量也有关;然后带牌,只和两种牌的数量有关;最后单牌、对子、三张和炸弹,只和数量有关。

首先因为可以打单张,这题是一定有解的,我们可以放心的搜下去。

关于顺子,我们通过生活经验可以发现,如果有几张数字连着的牌,最好使用顺子而不是单打,因为这样的解更小,更优。然后顺子里面也可以分类,假如我们有5 5 6 6 7 7 8 9几张牌,如果先打单顺子那么就会多不少单牌,所以我们要先打大的顺子,再打小的。最后因为顺子会拆掉不少牌型,需要注意顺子的长度也需要枚举,打不打也需要枚举,读者可以自己举几个例子想一想。

在我们枚举了顺子之后,就剩下了带牌和单张、对子等。因为带牌、单张等与数字无关,这时候我们可以把牌按数量分类。首先枚举带牌,因为单张、对子打出去会拆掉带牌,然后从长到短,四带两对,四带一对,三带对,三带一。最后只需要把所有无法打出带牌的牌直接丢出去即可——因为不管你的牌是一张到四张,按照本题的牌型可以一次打完。

这样我们理清了思路:深搜,枚举打顺子的状态,然后贪心带牌和单张、一对、三张、炸弹。最后需要注意的是,因为本题的手牌不止一副,我们需要在开始搜索之前重新初始化。开始敲代码吧 :)

于是AC代码是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstdio>
#include <cstring>
#define FOR(x,f,t) for(x=f;x<=t;++x)
#define RFOR(x,f,t) for(x=f;x>=t;--x)
#define MEMSET(a,b) memset(a,b,sizeof(a))
#define M 1000005
#define ll long long
#define oo 0x3f3f3f3f
using namespace std;
template<class T>void MAX(T &a,T b) {if(a<b)a=b;}
template<class T>void MIN(T &a,T b) {if(a>b)a=b;}
template<class T>void rd(T &a) { //读入外挂
char c;a=0;
while(c=getchar(),!isdigit(c));
do a=(a<<3)+(a<<1)+(c^48);
while(c=getchar(),isdigit(c));
}
int T,n;
int V[20]; //joker==0 2==2 3~K==3~13 A==14
int cnt[5]; //张数是i的牌的种类数量
int gao() { //处理散牌:炸弹,三张,对子,单张,带牌
MEMSET(cnt,0);
int i,j,ans=0;
FOR(i,0,14) cnt[V[i]]++;
while(cnt[4]>=1&&cnt[2]>=2) cnt[4]-=1, cnt[2]-=2, ans+=1; //4+2+2
while(cnt[4]>=1&&cnt[1]>=2) cnt[4]-=1, cnt[1]-=2, ans+=1; //4+1+1
while(cnt[3]>=1&&cnt[2]>=1) cnt[3]-=1, cnt[2]-=1, ans+=1; //3+2
while(cnt[3]>=1&&cnt[1]>=1) cnt[3]-=1, cnt[1]-=1, ans+=1; //3+1
ans+=cnt[4]+cnt[3]+cnt[2]+cnt[1]; //四张三张一对单张
return ans;
}
int dfs(int step) {
int i,j,k,t,ans=oo;
ans=gao(); //这句话代码意味深长。如果dfs到这里之后,已经没有顺子了,那么这时候只能贪心吃散牌,下面return的就是这个ans;如果还有顺子,那么下面顺子出来的结果一定会比ans小而覆盖掉这里。
//下面枚举状态的同时判断是不是终止状态(没顺子了),需要好好体会
FOR(i,3,14-2+1) { //3顺
k=0;
FOR(j,i,14+1) if(V[j]<3) {k=j-1;break;} //此时k为最大的三张连牌的结尾
if(k-i+1<2) continue; //如果连牌数量太小,不满足三顺子的条件,那就continue
//如果代码能执行到这里,说明[i,k]范围是一个合法的三顺子。
RFOR(t,k,i+2-1) { //枚举顺子长度。k-i+1即三顺子长度,可能会大于最大长度2。
FOR(j,i,t) V[j]-=3; //制造现场
MIN(ans,dfs(step+1)+1); //向下一层搜索
FOR(j,i,t) V[j]+=3; //还原现场
}
}
FOR(i,3,14-3+1) { //2顺
k=0;
FOR(j,i,14+1) if(V[j]<2) {k=j-1;break;}
if(k-i+1<3) continue;
RFOR(t,k,i+3-1) {
FOR(j,i,t) V[j]-=2;
MIN(ans,dfs(step+1)+1);
FOR(j,i,t) V[j]+=2;
}
}
FOR(i,3,14-5+1) { //1顺
k=0;
FOR(j,i,14+1) if(V[j]<1) {k=j-1;break;}
if(k-i+1<5) continue;
RFOR(t,k,i+5-1) {
FOR(j,i,t) V[j]-=1;
MIN(ans,dfs(step+1)+1);
FOR(j,i,t) V[j]+=1;
}
}
return ans;
}
int solve() {
return dfs(0);
}
int main () {
rd(T),rd(n);
int i,j;
FOR(i,1,T) {
int a,b;
MEMSET(V,0);
FOR(j,1,n){
rd(a);
if(a==1) a=14; //把A放到14,这样枚举顺子方便
V[a]++;
rd(b);
}
int ans=solve();
printf("%d\n",ans);
}
return 0;
}

by lmlstarqaq
with $2^{2^{n}}$ times of thanks to Spylft