题解：P2540 [NOIP2015 提高组] 斗地主 加强版

lihongru · 2025-01-25 15:36:50 · 题解

题目分析

这道题按照我们老师的话来说就是很神奇，写完才知道这道题有多么神奇。看到这道题依然只能想到搜索每一步出牌。

我们看题可以知道，牌的花色是不影响出牌的，所以输入时，我们不存每张牌长啥样，只存某种点数牌的数量，记作 s。

当然，输入需要特别把 1(A) 记在 15 的位置，这样才能更好的枚举顺子。以下分析均不带火箭，因为统计答案时直接使用更方便。

发现，有一部分出牌方法中，牌的点数和能否出是有关的，而另一部分中，牌的点数是无关的。我们依此大致可以把出牌分为两类。

• 顺子类：单顺子/双顺子/三顺子
• 其它类：炸弹/单张牌/对子牌/三张牌/三带一/三带二/四带二（需要拆解成四带二张和四带二对处理）

当然，不分类这道题依然可做，暴力卡时也能过。不过我更倾向于分类后使用这个“神奇”的剪枝来做。

牌的点数有关，我们没有什么好办法处理。但牌的点数无关就可以使用预处理的动态规划（四维：dp[单张数量][对子数量][三张数量][炸弹数量]）来减去搜索的时间复杂度。我们先来处理顺子类。

顺子类 - 搜索处理

我们使用暴力做法，暴力枚举顺子中每个点数的个数 a，起点位置 i 与可能的终点位置 j。对于每一个起点位置，我们开一个计数器 cnt 记成功选中的牌的点数个数。

对于每一个可能的终点位置 j，如果能够选择 a 张牌，则选择 a 张牌，并 cnt++;，如果不能，则直接跳出。

这里用数学直觉找出一个临界值用于判定，当顺子 cnt 足够时，a 和 cnt 满足 cnt \times a \ge 5，对于本题 a 的取值都是满足的。

由此可写出顺子部分的代码。注意删除和回溯。这份片段中，x 代表走到这一步需要的步数。

for (int a = 1; a <= 3; a++){
    for (int i = 3; i <= 14; i++){
        int cnt = 0;
        for (int j = i; j <= 14; j++){
            if (s[j] >= a) cnt++;
            else break;
            if (a * cnt >= 5){
                for (int k = i; k <= j; k++){
                    s[k] -= a;
                }
                dfs(x+1);
                for (int k = i; k <= j; k++){
                    s[k] += a;
                }
            }
        }

    }
}

其它类 - 动态规划

我们记 a 为单张数，b 为对子数，c 为三张数，d 为炸弹数。记 dp[a][b][c][d] 表示这些牌需要用几次出完。具体如何转移见下表。

注释：四带两张和四带两对都是四带二。所有带星号的都是拆牌操作，它们可能使得答案更优，且不需要消耗步数。

引入拆牌操作后，我们就需要仔细思考动态规划的顺序了。显然，d \to c \to b \to a 的顺序是更合理的，保证了每个值被推算前，它需要用到的值都已经推算完成。

预处理时进行动态规划即可。为了减少代码量，可以使用临时变量。注意边界问题，初始值的设置与 0 值不能够被覆盖。

for (int d = 0; d <= 5; d++){
    for (int c = 0; c <= 8; c++){
        for (int b = 0; b <= 12; b++){
            for (int a = 0; a <= 23; a++){
                if (!a && !b && !c && !d) continue;
                int s = 0x3f3f3f3f;

                if (a) s = min(s, dp[a-1][b][c][d] + 1);
                if (b) s = min(s, dp[a][b-1][c][d] + 1);
                if (c) s = min(s, dp[a][b][c-1][d] + 1);
                if (d) s = min(s, dp[a][b][c][d-1] + 1);

                if (a && c) s = min(s, dp[a-1][b][c-1][d] + 1);
                if (b && c) s = min(s, dp[a][b-1][c-1][d] + 1);
                if (a >= 2 && d) s = min(s, dp[a-2][b][c][d-1] + 1);
                if (b >= 2 && d) s = min(s, dp[a][b-2][c][d-1] + 1);

                if (b) s = min(s, dp[a+2][b-1][c][d]);
                if (c) s = min(s, dp[a+1][b+1][c-1][d]);
                if (d) s = min(s, dp[a][b+2][c][d-1]);
                if (d) s = min(s, dp[a+1][b][c+1][d-1]);

                dp[a][b][c][d] = s;
            }
        }
    }
}

剪枝的具体实现

由于牌一共就 14 种（不加大小王），我们直接暴力统计即可。调用时注意，双王可作单张，也可作火箭（即多加一步）。

memset(c, 0, sizeof c);
for (int i = 2; i <= 14; i++) c[s[i]]++;
ans = min(ans, x + dp[c[1]+s[0]][c[2]][c[3]][c[4]]);
if (s[0] == 2) ans = min(ans, x + dp[c[1]][c[2]][c[3]][c[4]] + 1);

当然，不要忘记我们的最简单的剪枝“最优性剪枝”。

if (x >= ans) return ;

最终将上面的代码块串在一起，加上输入输出就是本题的代码。

题目总结与参考代码

本题的“神奇之处”就在于使用动态规划进行剪枝。最后提醒一句，本题多测，不要忘记清空和重置答案。

#include <bits/stdc++.h>
using namespace std;

int T, n, s[25], c[5], dp[26][15][10][6], ans;

void dfs(int x){
    if (x >= ans) return ;

    memset(c, 0, sizeof c);
    for (int i = 2; i <= 14; i++) c[s[i]]++;
    ans = min(ans, x + dp[c[1]+s[0]][c[2]][c[3]][c[4]]);
    if (s[0] == 2) ans = min(ans, x + dp[c[1]][c[2]][c[3]][c[4]] + 1);

    for (int a = 1; a <= 3; a++){
        for (int i = 3; i <= 14; i++){
            int cnt = 0;
            for (int j = i; j <= 14; j++){
                if (s[j] >= a) cnt++;
                else break;
                if (a * cnt >= 5){
                    for (int k = i; k <= j; k++){
                        s[k] -= a;
                    }
                    dfs(x+1);
                    for (int k = i; k <= j; k++){
                        s[k] += a;
                    }
                }
            }

        }
    }
    return ;
}

int main(){
    for (int d = 0; d <= 5; d++){
        for (int c = 0; c <= 8; c++){
            for (int b = 0; b <= 12; b++){
                for (int a = 0; a <= 23; a++){
                    if (!a && !b && !c && !d) continue;
                    int s = 0x3f3f3f3f;

                    if (a) s = min(s, dp[a-1][b][c][d] + 1);
                    if (b) s = min(s, dp[a][b-1][c][d] + 1);
                    if (c) s = min(s, dp[a][b][c-1][d] + 1);
                    if (d) s = min(s, dp[a][b][c][d-1] + 1);

                    if (a && c) s = min(s, dp[a-1][b][c-1][d] + 1);
                    if (b && c) s = min(s, dp[a][b-1][c-1][d] + 1);
                    if (a >= 2 && d) s = min(s, dp[a-2][b][c][d-1] + 1);
                    if (b >= 2 && d) s = min(s, dp[a][b-2][c][d-1] + 1);

                    if (b) s = min(s, dp[a+2][b-1][c][d]);
                    if (c) s = min(s, dp[a+1][b+1][c-1][d]);
                    if (d) s = min(s, dp[a][b+2][c][d-1]);
                    if (d) s = min(s, dp[a+1][b][c+1][d-1]);

                    dp[a][b][c][d] = s;
                }
            }
        }
    }
    cin >> T >> n;
    while (T--){
        memset(s, 0, sizeof s);
        for (int i = 1; i <= n; i++){
            int x, y; cin >> x >> y;
            if (x == 1) x = 14;
            s[x]++;
        }
        ans = 0x7f7f7f7f;
        dfs(0);
        cout << ans << endl;
    }
    return 0;
}