[NOIP 2015 提高组] 斗地主

GitHub 跳转原题关系图返回列表

先在外层 DFS 枚举单顺、双顺、三顺的拆法，再对剩余牌型做记忆化搜索，精确求出最少出牌次数。

OJ: luogu

题目 ID: P2668

难度:提高+/省选-

标签:搜索记忆化搜索DFS状态压缩思维

日期: 2026-06-20 21:10

题意

给出若干组手牌，每组有 n 张。

每次可以按题目给定的合法牌型打出一手牌，目标是让总出牌次数最少。

本题只关心最少要打多少手，不考虑和对手比大小。

思路

先看一个最容易理解的小数据暴力：

cpp

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200#include <bits/stdc++.h>
using namespace std;

const int RANK_CNT = 16;

int T, n;
int cnt[RANK_CNT];
int answer;

int rank_id(int a) {
    if (a == 0) {
        return 14;
    }
    if (a == 1) {
        return 12;
    }
    if (a == 2) {
        return 13;
    }
    return a - 2;
}

bool empty_hand() {
    for (int i = 1; i <= 15; i++) {
        if (cnt[i] != 0) {
            return false;
        }
    }
    return true;
}

void dfs(int step) {
    if (step >= answer) {
        return;
    }
    if (empty_hand()) {
        answer = step;
        return;
    }

    for (int i = 1; i <= 15; i++) {
        if (cnt[i] == 0) {
            continue;
        }

        cnt[i]--;
        dfs(step + 1);
        cnt[i]++;

        if (cnt[i] >= 2) {
            cnt[i] -= 2;
            dfs(step + 1);
            cnt[i] += 2;
        }

        if (cnt[i] >= 3) {
            cnt[i] -= 3;
            dfs(step + 1);

            for (int j = 1; j <= 15; j++) {
                if (cnt[j] >= 1) {
                    cnt[j]--;
                    dfs(step + 1);
                    cnt[j]++;
                }
            }

            for (int j = 1; j <= 15; j++) {
                if (cnt[j] >= 2) {
                    cnt[j] -= 2;
                    dfs(step + 1);
                    cnt[j] += 2;
                }
            }

            cnt[i] += 3;
        }

        if (cnt[i] >= 4) {
            cnt[i] -= 4;
            dfs(step + 1);

            for (int a = 1; a <= 15; a++) {
                if (cnt[a] == 0) {
                    continue;
                }
                cnt[a]--;
                for (int b = a; b <= 15; b++) {
                    if (cnt[b] == 0) {
                        continue;
                    }
                    cnt[b]--;
                    dfs(step + 1);
                    cnt[b]++;
                }
                cnt[a]++;
            }

            for (int a = 1; a <= 15; a++) {
                if (cnt[a] < 2) {
                    continue;
                }
                cnt[a] -= 2;
                for (int b = a; b <= 15; b++) {
                    if (cnt[b] < 2) {
                        continue;
                    }
                    cnt[b] -= 2;
                    dfs(step + 1);
                    cnt[b] += 2;
                }
                cnt[a] += 2;
            }

            cnt[i] += 4;
        }
    }

    if (cnt[14] >= 1 && cnt[15] >= 1) {
        cnt[14]--;
        cnt[15]--;
        dfs(step + 1);
        cnt[14]++;
        cnt[15]++;
    }

    for (int l = 1; l <= 12; l++) {
        if (cnt[l] == 0) {
            continue;
        }
        for (int r = l; r <= 12 && cnt[r] >= 1; r++) {
            if (r - l + 1 < 5) {
                continue;
            }
            for (int i = l; i <= r; i++) {
                cnt[i]--;
            }
            dfs(step + 1);
            for (int i = l; i <= r; i++) {
                cnt[i]++;
            }
        }
    }

    for (int l = 1; l <= 12; l++) {
        if (cnt[l] < 2) {
            continue;
        }
        for (int r = l; r <= 12 && cnt[r] >= 2; r++) {
            if (r - l + 1 < 3) {
                continue;
            }
            for (int i = l; i <= r; i++) {
                cnt[i] -= 2;
            }
            dfs(step + 1);
            for (int i = l; i <= r; i++) {
                cnt[i] += 2;
            }
        }
    }

    for (int l = 1; l <= 12; l++) {
        if (cnt[l] < 3) {
            continue;
        }
        for (int r = l; r <= 12 && cnt[r] >= 3; r++) {
            if (r - l + 1 < 2) {
                continue;
            }
            for (int i = l; i <= r; i++) {
                cnt[i] -= 3;
            }
            dfs(step + 1);
            for (int i = l; i <= r; i++) {
                cnt[i] += 3;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T >> n;
    while (T--) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++) {
            int a, b;
            cin >> a >> b;
            cnt[rank_id(a)]++;
        }
        answer = n;
        dfs(0);
        cout << answer << '\n';
    }

    return 0;
}

brute.cpp 直接从当前手牌枚举所有合法出牌方式，然后递归搜索最少步数。

这个做法很直观，但会遇到两个问题：

同一个剩余状态会被重复搜索很多次；
顺子类牌型是连续区间，和普通牌型混在一起枚举会很乱。

所以正式解把问题拆成两层。

第一层，先枚举顺子类牌型：

单顺
双顺
三顺

顺子类的共同特点是都作用在一段连续区间上，因此很适合作为外层 DFS 的分支。

第二层，当我们决定“当前不再继续拆顺子”后，剩余问题只需要处理这些非顺子牌型：

单张
对子
三张
三带一
三带二
炸弹
火箭
四带二

这时状态只和“每个点数还剩几张牌”有关，和花色已经完全无关了。

因此可以把整组手牌压成计数数组 cnt[i]，再用记忆化搜索求这个状态的最优值。

正式解的结构就是：

dfs_straight()：枚举所有可能的顺子类拆法；
solve_rest()：对当前剩余状态做记忆化搜索，精确求非顺子部分的最优解；
两者结合，得到全局最优答案。

这里还有一个很关键的细节：

顺子不能包含 2 和大小王

所以代码里顺子只会枚举到 A 为止。

代码

cpp

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243#include <bits/stdc++.h>
using namespace std;

const int RANK_CNT = 16;

int T, n;
int cnt[RANK_CNT];
int answer;
map<long long, int> memo;

// 把 3..A,2,小王,大王 映射到 1..15，方便顺子判断。
int rank_id(int a) {
    if (a == 0) {
        return 14;
    }
    if (a == 1) {
        return 12;
    }
    if (a == 2) {
        return 13;
    }
    return a - 2;
}

long long encode_state() {
    long long code = 0;
    for (int i = 1; i <= 15; i++) {
        code = code * 5 + cnt[i];
    }
    return code;
}

// 不再考虑顺子时，剩余牌型的最优解。
int solve_rest() {
    long long state = encode_state();
    map<long long, int>::iterator it = memo.find(state);
    if (it != memo.end()) {
        return it->second;
    }

    int single_cnt = 0;
    int pair_cnt = 0;
    int best = 0;

    for (int i = 1; i <= 15; i++) {
        if (cnt[i] == 1) {
            single_cnt++;
        } else if (cnt[i] == 2) {
            pair_cnt++;
        } else if (cnt[i] == 3) {
            best++;
        } else if (cnt[i] == 4) {
            best++;
        }
    }

    // 三张/炸弹尽量带牌，可以把剩下的单牌或对子吸收进去。
    for (int i = 1; i <= 15; i++) {
        if (cnt[i] == 3) {
            if (pair_cnt > 0) {
                pair_cnt--;
            } else if (single_cnt > 0) {
                single_cnt--;
            }
        } else if (cnt[i] == 4) {
            if (pair_cnt >= 2) {
                pair_cnt -= 2;
            } else if (pair_cnt >= 1 && single_cnt >= 1) {
                pair_cnt--;
                single_cnt--;
            } else if (single_cnt >= 2) {
                single_cnt -= 2;
            }
        }
    }

    best += pair_cnt + single_cnt;

    // 再尝试更精细地枚举三张/炸弹的出法，修正上面的贪心估值。
    for (int i = 1; i <= 15; i++) {
        if (cnt[i] >= 3) {
            cnt[i] -= 3;
            best = min(best, solve_rest() + 1);

            for (int j = 1; j <= 15; j++) {
                if (cnt[j] >= 1) {
                    cnt[j]--;
                    best = min(best, solve_rest() + 1);
                    cnt[j]++;
                }
            }

            for (int j = 1; j <= 15; j++) {
                if (cnt[j] >= 2) {
                    cnt[j] -= 2;
                    best = min(best, solve_rest() + 1);
                    cnt[j] += 2;
                }
            }

            cnt[i] += 3;
        }

        if (cnt[i] == 4) {
            cnt[i] -= 4;
            best = min(best, solve_rest() + 1);

            for (int a = 1; a <= 15; a++) {
                if (cnt[a] == 0) {
                    continue;
                }
                cnt[a]--;
                for (int b = a; b <= 15; b++) {
                    if (cnt[b] == 0) {
                        continue;
                    }
                    cnt[b]--;
                    best = min(best, solve_rest() + 1);
                    cnt[b]++;
                }
                cnt[a]++;
            }

            for (int a = 1; a <= 15; a++) {
                if (cnt[a] < 2) {
                    continue;
                }
                cnt[a] -= 2;
                for (int b = a; b <= 15; b++) {
                    if (cnt[b] < 2) {
                        continue;
                    }
                    cnt[b] -= 2;
                    best = min(best, solve_rest() + 1);
                    cnt[b] += 2;
                }
                cnt[a] += 2;
            }

            cnt[i] += 4;
        }
    }

    if (cnt[14] >= 1 && cnt[15] >= 1) {
        cnt[14]--;
        cnt[15]--;
        best = min(best, solve_rest() + 1);
        cnt[14]++;
        cnt[15]++;
    }

    memo[state] = best;
    return best;
}

// depth 表示已经打出了多少手顺子类牌型。
void dfs_straight(int depth) {
    if (depth >= answer) {
        return;
    }

    answer = min(answer, depth + solve_rest());

    // 单顺子：长度至少 5，只能用到 A，不能含 2 和大小王。
    for (int l = 1; l <= 12; l++) {
        if (cnt[l] == 0) {
            continue;
        }
        for (int r = l; r <= 12 && cnt[r] >= 1; r++) {
            if (r - l + 1 < 5) {
                continue;
            }
            for (int i = l; i <= r; i++) {
                cnt[i]--;
            }
            dfs_straight(depth + 1);
            for (int i = l; i <= r; i++) {
                cnt[i]++;
            }
        }
    }

    // 双顺子：长度至少 3。
    for (int l = 1; l <= 12; l++) {
        if (cnt[l] < 2) {
            continue;
        }
        for (int r = l; r <= 12 && cnt[r] >= 2; r++) {
            if (r - l + 1 < 3) {
                continue;
            }
            for (int i = l; i <= r; i++) {
                cnt[i] -= 2;
            }
            dfs_straight(depth + 1);
            for (int i = l; i <= r; i++) {
                cnt[i] += 2;
            }
        }
    }

    // 三顺子：长度至少 2。
    for (int l = 1; l <= 12; l++) {
        if (cnt[l] < 3) {
            continue;
        }
        for (int r = l; r <= 12 && cnt[r] >= 3; r++) {
            if (r - l + 1 < 2) {
                continue;
            }
            for (int i = l; i <= r; i++) {
                cnt[i] -= 3;
            }
            dfs_straight(depth + 1);
            for (int i = l; i <= r; i++) {
                cnt[i] += 3;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T >> n;
    while (T--) {
        memset(cnt, 0, sizeof(cnt));

        for (int i = 1; i <= n; i++) {
            int a, b;
            cin >> a >> b;
            cnt[rank_id(a)]++;
        }

        memo.clear();
        answer = n;
        dfs_straight(0);
        cout << answer << '\n';
    }

    return 0;
}

复杂度

这题的复杂度很难写成一个紧致公式，因为搜索规模和手牌结构强相关。

从实现上看：

外层 DFS 枚举顺子类拆法
内层记忆化避免同一状态重复计算

在 n <= 23 且数据随机的条件下可以通过。

总结

这题的重点不是把所有牌型硬塞进一个 DFS 里暴搜，而是先把最难处理的“连续顺子类”拆出来，再把剩余状态压成“每个点数剩几张”的记忆化搜索问题。

这样结构会清楚很多，也更容易写对。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P2668 [NOIP 2015 提高组] 斗地主

题目背景

NOIP2015 Day1T3

题目描述

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

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

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

本题数据随机，不支持hack，要hack或强力数据请点击这里。

输入格式

第一行包含用空格隔开的 $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

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

说明/提示

样例 1 说明

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

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

测试点编号	$T=$	$n=$
1	$100$	$2$
2	$100$	$2$
3	$100$	$3$
4	$100$	$3$
5	$100$	$4$
6	$100$	$4$
7	$100$	$10$
8	$100$	$11$
9	$100$	$12$
10	$100$	$13$
11	$100$	$14$
12	$100$	$15$
13	$10$	$16$
14	$10$	$17$
15	$10$	$18$
16	$10$	$19$
17	$10$	$20$
18	$10$	$21$
19	$10$	$22$
20	$10$	$23$

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

[NOIP 2015 提高组] 斗地主

目录

题意

思路

代码

复杂度

总结

一图流解析