前言

一看到题目
woc，这TM什么题目

对于我一个打牌10局输11局的蒟蒻来说

简直是送命题啊！！！

但仔细想想，好像可以暴力模拟啊！QWQ

30分做法

仔细想想自己打牌的时候，是不是喜欢先出顺子，再出三带，最后出对或者单张

没有错（柯南时刻，推一下眼镜，虽然我没有），这个就是贪心思想

我们是不是可以让程序也这样做

显然这样是片面最优的，所以也只能拿30分。。。

（但我的程序跑了35分。。。）

30分代码：（代码一共194行，长度警告）

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

int T, n;
int a, x;  //b[x][y]表示码数为x的牌的花色 
int card[15], used[15];  //card[i]记录码数为i的牌的数量；used储存顺子的顺序 
int order[15] = {0, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 2, 0};  //牌大小顺序 
int ans = 0;

void DelCard (int ctrl, int num) {  //删牌
//ctrl 为删牌类型，单顺子为1，双顺子2，三顺子3 
    if (ctrl == 1) {
        for (int i = 1; i <= num; i ++) {
            card[used[i]] --;
        }
        ans ++;
    }
    if (ctrl == 2) {
        for (int i = 1; i <= num; i ++) {
            card[used[i]] -= 2;
        }
        ans ++; 
    }
    if (ctrl == 3) {
        for (int i = 1; i <= num; i ++) {
            card[used[i]] -= 3;
        }
        ans ++;
    }
    if (ctrl == 4) {  //减单张牌 
        for (int i = 1; i <= num; i ++) {
            card[used[i]] --;
        }
    }
}

void dfs (int x, int ctrl, int step) {
//ctrl 表示dfs顺子类型，单顺子为1，双顺子为2，三顺子为3
    if (ctrl == 1) {
        used[step] = order[x];  //加入顺子队列 
        if (card[order[x + 1]] >= 1 && x + 1 < 13) {
            dfs (x + 1, 1, step + 1);
        } else {
            if (step >= 5) DelCard (1, step);
        }
    }
    if (ctrl == 2) {
        used[step] = order[x];  //加入顺子队列 
        if (card[order[x + 1]] >= 2 && x + 1 < 13) {
            dfs (x + 1, 2, step + 1);
        } else {
            if (step >= 3) DelCard (2, step);
        }
    }
    if (ctrl == 3) {
        used[step] = order[x];  //加入顺子队列 
        if (card[order[x + 1]] >= 3 && x + 1 < 13) {
            dfs (x + 1, 3, step + 1);
        } else {
            if (step >= 2) DelCard (3, step);
        }
    }
}

void sovle () {
    for (int i = 1; i <= 12; i ++) {  //找三顺子 
        memset (used, 0, sizeof (used));
        if (card[order[i]] >= 3) dfs (i, 3, 1);
    }
    for (int i = 1; i <= 11; i ++) {  //找双顺子 
        memset (used, 0, sizeof (used));
        if (card[order[i]] >= 2) dfs (i, 2, 1);
    }
    for (int i = 1; i <= 9; i ++) {  //找单顺子 
        memset (used, 0, sizeof (used));
        if (card[order[i]] >= 1) dfs (i, 1, 1);
    }
    for (int i = 1; i < 14; i ++) {  //找四带二 or 炸弹 
        if (card[order[i]] == 4) {
            bool allow1 = false, allow2 = false, allow3 = false;  //allow1 带两张单牌；allow2 带一对牌；allow3带两对牌 
            int p, p3[15], num1 = 0, num2 = 0;
            memset (used, 0, sizeof (used));
            for (int j = 1; j <= 14; j ++) {  //找带两张牌 
                if (card[order[j]] == 1 && j != i) {
                    num1 ++;
                    used[num1] = order[j];
                }
                if (card[order[j]] == 2 && j != i) {
                    num2 ++;
                    p3[num2] = j;
                    p = j;
                    allow2 = true;
                }
                if (num1 >= 2) {
                    allow1 = true;
                }
                if (num2 >= 2) {
                    allow3 = true;
                    break;
                }
            }
            if (allow3 == true) {
                card[order[i]] -= 4;
                for (int j = 1; j <= 2; j ++) card[order[p3[j]]] -=2;
                ans ++;
                continue;
            } else if (allow1 == true) {
                card[order[i]] -= 4;
                DelCard (4, 2);
                ans ++;
                continue;
            } else if (allow2 == true) {
                card[order[i]] -= 4;
                card[order[p]] -=2;
                ans ++;
                continue;
            } else {
                card[order[i]] -= 4;
                ans ++;
                continue;
            }
        }
    }
    for (int i = 1; i < 14; i ++) {  //找三带 
        if (card[order[i]] >= 3) {
            bool allow1 = false, allow2 = false;  //allow1 带一；allow1 带二 
            int p, num = 0;
            memset (used, 0, sizeof (used));
            for (int j = 1; j <= 14; j ++) {  //找带二 
                if (card[order[j]] == 2 && j != i) {
                    p = j;
                    allow2 = true;
                    break; 
                }
            }
            //memset (used, 0, sizeof (used));
            num = 0;
            for (int j = 1; j <= 14; j ++) {  //找带一 
                if (card[order[j]] == 1 && j != i && allow2 == false) {
                    num ++;
                    used[num] = order[j];
                    allow1 = true;
                    break; 
                }
            }
            if (allow2 == true) {  //删三带二 
                card[order[i]] -= 3;
                card[order[p]] -= 2;
                ans ++;
                continue;
            } else if (allow1 == true) {  //删三带一 
                card[order[i]] -= 3;
                DelCard (4, num);
                ans ++;
                continue;
            } else {  //删三张牌 
                card[order[i]] -= 3;
                ans ++;
                continue;
            }
        }
    }
    for (int i = 1; i <= 14; i ++) {  //找两张牌 or 火箭 
        if (card[order[i]] >= 2) {
            card[order[i]] -= 2;
            ans ++;
        }
    }
    for (int i = 1; i <= 14; i ++) {  //找单张牌
        if (card[order[i]] >= 1) {
            card[order[i]] --;
            ans ++;
        }
    }
    printf ("%d\n", ans);
}

int main () {
    //freopen ("landlords.in", "r", stdin);
    //freopen ("landlords.out", "w", stdout);
    scanf ("%d%d", &T, &n);
    for (int k = 0; k < T; k ++) {
        memset (card, 0, sizeof (card));
        ans = 0;
        for (int l = 0; l < n; l ++) {
            scanf ("%d", &a);
            card[a] ++;
            scanf ("%d", &x);
        }
        sovle ();
    }
    //fclose (stdin); fclose (stdout);
    return 0;
}

满分做法

显然30分不能满足我们OIer的需求

所以，进过我的苦思冥想，掉了不知多少根头发

终于，我打出了伪代码

又调试了很久，将所有情况都枚举出来，终于AC了（T_T）

告诫我们做事要细心，不然会。。。

言归正传

有了刚才的贪心，我们是不是可以优化的一下

运用一下深度优先搜索（广搜也可以，但是我不会表示状态。。。）

将每一种情况的步数都搜索出来

在输出最小值就可以了

特别说明一下

可以判断当前步数如果已经大于ans了，就直接return，达到剪枝的效果（其实不剪枝应该也可以过）

在查找各个情况的代码中也可以适当剪枝（具体看代码），每种情况我都有注释

PS：我的码风偏向公司类型，喜欢模块化

满分代码：（代码一共266行，超长警告）

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

int T, n;
int a, b;
int card[15];  //card[i]记录码数为i的牌的数量；used储存用过牌的码数 
int order[15] = {0, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 2, 0};  //牌大小顺序 
int ans;

void dfs (int step, int cardtol);

void SingleStraight (int step, int cardtol) {  //单顺子
    for (int i = 1; i <= 9; i ++) {
        int num = 0;
        while (card[order[i + num]] >= 1 && i + num <= 12) {
            num ++;
            if (num >= 5) {
                for (int j = i; j < i + num; j ++) card[order[j]] --;
                dfs (step + 1, cardtol - num);
                for (int j = i; j < i + num; j ++) card[order[j]] ++;
                //break;
            }
        }
    }
}

void DoubleStraight (int step, int cardtol) {  //双顺子
    for (int i = 1; i <= 11; i ++) {
        int num = 0;
        while (card[order[i + num]] >= 2 && i + num <= 12) {
            num ++;
            if (num >= 3) {
                for (int j = i; j < i + num; j ++) card[order[j]] -= 2;
                dfs (step + 1, cardtol - 2 * num);
                for (int j = i; j < i + num; j ++) card[order[j]] += 2;
                //break;
            }
        }
    }
}

void TripleStraight (int step, int cardtol) {  //三顺子
    for (int i = 1; i <= 12; i ++) {
        int num = 0;
        while (card[order[i + num]] >= 3 && i + num <= 12) {
            num ++;
            if (num >= 2) {
                for (int j = i; j < i + num; j ++) card[order[j]] -= 3;
                dfs (step + 1, cardtol - 3 * num);
                for (int j = i; j < i + num; j ++) card[order[j]] += 3;
                //break;
            }
        }
    }
}

void FourWithTwoPair (int step, int cardtol) {  //四带两对 
    int num = 0, used[15] = {0};
    for (int i = 1; i <= 14; i ++) {
        if (card[order[i]] >= 2 && card[order[i]] < 4) {
            num ++;
            used[num] = order[i];
        }
    }
    if (num < 2) return;
    for (int i = 1; i < 14; i ++) {
        if (card[order[i]] == 4) {
            card[order[i]] -= 4;
            for (int j = 1; j < num; j ++) {
                card[used[j]] -= 2;
                for (int k = j + 1; k <= num; k ++) {
                    card[used[k]] -= 2;
                    dfs (step + 1, cardtol - 8);
                    card[used[k]] += 2;
                }
                card[used[j]] += 2;
            }
            card[order[i]] += 4;
            break;
        }
    }
}

void FourWithPair (int step, int cardtol) {  //四带一对 
    int num = 0, used[15] = {0};
    for (int i = 1; i <= 14; i ++) {
        if (card[order[i]] >= 2 && card[order[i]] < 4) {
            num ++;
            used[num] = order[i];
        }
    }
    if (num == 0) return;
    for (int i = 1; i < 14; i ++) {
        if (card[order[i]] == 4) {
            card[order[i]] -= 4;
            for (int j = 1; j <= num; j ++) {
                card[used[j]] -= 2;
                dfs (step + 1, cardtol - 6);
                card[used[j]] += 2;
            }
            card[order[i]] += 4;
            break;
        }
    }
}

void FourWithTwo (int step, int cardtol) {  //四带二
    int num = 0, used[15] = {0};
    for (int i = 1; i <= 14; i ++) {
        if (card[order[i]] >= 1 && card[order[i]] < 4) {
            num ++;
            used[num] = order[i];
        }
    }
    if (num < 2) return;
    for (int i = 1; i < 14; i ++) {
        if (card[order[i]] == 4) {
            card[order[i]] -= 4;
            for (int j = 1; j < num; j ++) {
                card[used[j]] --;
                for (int k = j + 1; k <= num; k ++) {
                    card[used[k]] --;
                    dfs (step + 1, cardtol - 6);
                    card[used[k]] ++;
                }
                card[used[j]] ++;
            }
            card[order[i]] += 4;
            break;
        }
    }
}

void Four (int step, int cardtol) {  //炸弹 
    int used[15] = {0};
    for (int i = 1; i < 14; i ++) {
        if (card[order[i]] == 4) {
            card[order[i]] -= 4;
            dfs (step + 1, cardtol - 4);
            card[order[i]] += 4;
            break;
        }
    }
}

void ThreeWithPair (int step, int cardtol) {  //三带二
    int num = 0, used[15] = {0};
    for (int i = 1; i <= 14; i ++) {
        if (card[order[i]] == 2) {
            num ++;
            used[num] = order[i];
        }
    }
    if (num == 0) return;
    for (int i = 1; i < 14; i ++) {
        if (card[order[i]] >= 3) {
            card[order[i]] -= 3;
            card[used[1]] -= 2;
            dfs (step + 1, cardtol - 5);
            card[order[i]] += 3;
            card[used[1]] += 2;
            break;
        }
    }
}

void ThreeWithOne (int step, int cardtol) {  //三带一 
    int num = 0, used[15] = {0};
    for (int i = 1; i <= 14; i ++) {
        if (card[order[i]] >= 1 && card[order[i]] < 3) {
            num ++;
            used[num] = order[i];
        }
    }
    if (num == 0) return;
    for (int i = 1; i < 14; i ++) {
        if (card[order[i]] >= 3) {
            card[order[i]] -= 3;
            card[used[1]] --;
            dfs (step + 1, cardtol - 4);
            card[order[i]] += 3;
            card[used[1]] ++;
            break;
        }
    }
}

void Three (int step, int cardtol) {  //三张牌
    for (int i = 1; i < 14; i ++) {
        if (card[order[i]] >= 3) {
            card[order[i]] -= 3;
            dfs (step + 1, cardtol - 3);
            card[order[i]] += 3;
            break;
        }
    }
}

void Pair (int step, int cardtol) {  //对子 or 火箭
    for (int i = 1; i <= 14; i ++) {
        if (card[order[i]] >= 2) {
            card[order[i]] -= 2;
            dfs (step + 1, cardtol - 2);
            card[order[i]] += 2;
            break;
        }
    }
}

void Single (int step, int cardtol) {  //一张牌 
    for (int i = 1; i <= 14; i ++) {
        if (card[order[i]] >= 1) {
            card[order[i]] -= 1;
            dfs (step + 1, cardtol - 1);
            card[order[i]] += 1;
            break;
        }
    }
}

void dfs (int step, int cardtol) {
    if (cardtol == 0) ans = min (ans, step - 1);
    if (step - 1 >= ans) return;  //剪枝
    if (cardtol < 0) return;

    //找顺子 
    if (cardtol >= 6) TripleStraight (step, cardtol);
    if (cardtol >= 6) DoubleStraight (step, cardtol);
    if (cardtol >= 5) SingleStraight (step, cardtol);

    //找四张牌 
    if (cardtol >= 8) FourWithTwoPair (step, cardtol);
    if (cardtol >= 6) FourWithPair (step, cardtol);
    if (cardtol >= 6) FourWithTwo (step, cardtol);
    if (cardtol >= 4) Four (step, cardtol);

    //三张牌 
    if (cardtol >= 5) ThreeWithPair (step, cardtol);
    if (cardtol >= 4) ThreeWithOne (step, cardtol);
    if (cardtol >= 3) Three (step, cardtol);

    //两张牌 or 火箭 
    if (cardtol >= 2) Pair (step, cardtol);

    //一张牌
    Single (step, cardtol); 
}

int main() {
    //freopen ("landlords.in", "r", stdin);
    //freopen ("landlords.out", "w", stdout);
    scanf ("%d%d", &T, &n);
    for (int k = 0; k < T; k ++) {
        memset (card, 0, sizeof (card));
        ans = n; 
        for (int l = 0; l < n; l ++) {
            scanf ("%d", &a);
            card[a] ++;
            scanf ("%d", &b);
        }
        dfs (1, n);
        printf ("%d\n", ans);
    }
    //fclose (stdin); fclose (stdout);
    return 0;
}

这个代码跑加强版可以跑92分，有一个点被T了，还有几个点WA，估计又有什么情况没有讨论到了（调一下）

题目链接：

Luogu P2668

稳健 Online Judge TK10199