洛谷P2540 斗地主增强版

23 August 2019 | duanyll | Tags: OI 题解 搜索

一道经典的搜索?题, 早就想做了.

听说考试原题的数据很水, 瞎贪心都能过, 就不说了, 这里分析一下几个直接贪心不能解决的地方.

• 两个鬼是否拆开(3333鬼鬼)
• 顺子要截取多少(日常斗地主经验太常见这种情况了)
• 炸弹和三联拆不拆开(33334444, 理解成四带两对可以一次走掉)
• 多次顺子/拆炸弹

按照以上几个痛点依次dfs搜索就是了, 具体见代码

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
using namespace std;

typedef long long int64;

const int INF = 0x3f3f3f3f;
const int MAXN = 25;

typedef int card;

const card three = 1;
const card four = 2;
const card five = 3;
const card six = 4;
const card seven = 5;
const card eight = 6;
const card nine = 7;
const card ten = 8;
const card J = 9;
const card Q = 10;
const card K = 11;
const card A = 12;
const card two = 13;
const card grey_joker = 14;
const card red_joker = 15;

card parse(int a, int b) {
    switch (a) {
        case 0:
            if (b == 1)
                return grey_joker;
            else
                return red_joker;
        case 1:
            return A;
        case 2:
            return two;
        case 3:
            return three;
        case 4:
            return four;
        case 5:
            return five;
        case 6:
            return six;
        case 7:
            return seven;
        case 8:
            return eight;
        case 9:
            return nine;
        case 10:
            return ten;
        case 11:
            return J;
        case 12:
            return Q;
        case 13:
            return K;
        default:
            clog << "fuck unknown card" << endl;
            return 0;
    }
}

int n;
int card_count[20];
int style_count[5];

// 考虑最后的情况(贪心匹配)
int get_other() {
    int tmp[5];
    memcpy(tmp, style_count, sizeof tmp);
    int ans = 0;
    while (tmp[4] > 0) {
        tmp[4]--;
        ans++;
        if (tmp[1] >= 2) {  // 带两张单牌
            tmp[1] -= 2;
        } else if (tmp[2] >= 2) {  // 带两对
            tmp[2] -= 2;
        } else if (tmp[2] >= 1) {  // 带一对
            tmp[2]--;
        }
    }
    while (tmp[3] > 0) {
        tmp[3]--;
        ans++;
        if (tmp[1] >= 1) {  // 带一张单牌
            tmp[1]--;
        } else if (tmp[2] >= 1) { // 带一对
            tmp[2]--;
        }
    }
    ans += tmp[2] + tmp[1];
    return ans;
}

// 考虑拆开对子和三连, 炸弹
int dfs_break() {
    int ans = INF;

    // 不拆
    ans = min(ans, get_other());

    // 拆对子 (没意义)
    // if (style_count[2] > 0) {
    //     style_count[2]--;
    //     style_count[1] += 2;
    //     ans = min(ans, get_other());
    //     style_count[1] -= 2;
    //     style_count[2]++;
    // }

    // 拆三联
    if (style_count[3] > 0) {
        style_count[3]--;
        style_count[2]++;
        style_count[1]++;
        ans = min(ans, dfs_break());
        style_count[1]--;
        style_count[2]--;
        style_count[3]++;
    }

    // 拆炸弹
    if (style_count[4] > 0) {
        style_count[4]--;

        style_count[2] += 2;
        ans = min(ans, dfs_break());
        style_count[2] -= 2;

        style_count[1]++;
        style_count[3]++;
        ans = min(ans, dfs_break());
        style_count[3]--;
        style_count[1]--;

        style_count[4]++;
    }

    return ans;
}

// 考虑三种顺子
int dfs_sequence() {
    int ans = INF;

    // 不出顺子
    memset(style_count, 0, sizeof style_count);
    for (card i = three; i <= red_joker; i++) {
        style_count[card_count[i]]++;
    }
    ans = min(ans, dfs_break());

    // 考虑单顺子
    for (card i = three; i + 4 < two; i++) {
        for (card j = i; j < two; j++) {
            if (card_count[j] < 1) break;
            if (j - i < 4) continue;
            for (card k = i; k <= j; k++) {
                card_count[k] -= 1;
            }
            ans = min(ans, dfs_sequence() + 1);
            for (card k = i; k <= j; k++) {
                card_count[k] += 1;
            }
        }
    }

    // 考虑双顺子
    for (card i = three; i + 2 < two; i++) {
        for (card j = i; j < two; j++) {
            if (card_count[j] < 2) break;
            if (j - i < 2) continue;
            for (card k = i; k <= j; k++) {
                card_count[k] -= 2;
            }
            ans = min(ans, dfs_sequence() + 1);
            for (card k = i; k <= j; k++) {
                card_count[k] += 2;
            }
        }
    }

    // 考虑三顺子
    for (card i = three; i + 1 < two; i++) {
        for (card j = i; j < two; j++) {
            if (card_count[j] < 3) break;
            if (j - i < 1) continue;
            for (card k = i; k <= j; k++) {
                card_count[k] -= 3;
            }
            ans = min(ans, dfs_sequence() + 1);
            for (card k = i; k <= j; k++) {
                card_count[k] += 3;
            }
        }
    }

    return ans;
}

// 是否出对鬼
int dfs_joker() {
    int ans = INF;
    if (card_count[grey_joker] > 0 && card_count[red_joker] > 0) {
        card_count[grey_joker]--;
        card_count[red_joker]--;
        ans = min(ans, dfs_sequence() + 1);
        card_count[grey_joker]++;
        card_count[red_joker]++;
    }
    ans = min(ans, dfs_sequence());
    return ans;
}

int main() {
    int tcnt;
    cin >> tcnt >> n;
    for (int T = 1; T <= tcnt; T++) {
        memset(card_count, 0, sizeof card_count);
        for (int i = 1; i <= n; i++) {
            int a, b;
            cin >> a >> b;
            card_count[parse(a, b)]++;
        }
        cout << dfs_joker() << endl;
    }
    // ans = INF;
    return 0;
}

这题要是放cf educational round上会不会全场fst…