本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-17 14:37:37

纯纯大模拟+DFS+贪心。

这个题要注意的细节挺多的（交了10发，一上午才过）。

打过扑克的都知道，顺子一次能出最多的牌，三带一四带二其次，对子炸弹和单牌在最后。 我们可以以此来进行贪心。

我们先判断顺子，分为三种情况：单，双，三。

我们可以从3开始，一直查到A，

然后是带（三带一之类的），我们先找到三张以上的牌，再继续从3查到大小王，只要有一张就可以深搜。但是注意，三 和 带一 的点不能相同，不然就是炸弹了。（3张5不能带上1张5，这种情况后面判断）。

注意：四带二分为两种情况，带两张单牌和两张对子。

在最后，我们不难发现，剩下的牌每一种点都能一次出去，所以只需要统计有多少种点就是还要几步。

细节：

• 这里我们用桶来存牌的点，从3到K都正常存，A存 $t_{14}$,2存 $t_{15}$，大小王存 $t_{16}$，$t_1$ 和 $t_2$ 不存。

• x循环遍历时，i,j,k三个变量及其容易弄混，本人就因为这找了大半个上午。

• 整个DFS都别忘了回溯。

代码赠详细解析

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int N=20;
long long n,k;
int t[N];
int minn;
void dfs(int x){\/\/别忘了回溯
    if(x>=minn) return ;\/\/剪枝优化
    int k=0;\/\/单顺子的长度
    for(int i=3;i<=14;i++){
        if(t[i]==0) k=0;
        else{
            k++;
            if(k>=5){
                for(int j=i-k+1;j<=i;j++) t[j]--;
                dfs(x+1);
                for(int j=i-k+1;j<=i;j++) t[j]++;\/\/回溯
            }
        }
    }
    k=0;\/\/双顺子的长度
    for(int i=3;i<=14;i++){
        if(t[i]<=1) k=0;
        else{
            k++;
            if(k>=3){
                for(int j=i-k+1;j<=i;j++) t[j]-=2;
                dfs(x+1);
                for(int j=i-k+1;j<=i;j++) t[j]+=2;
            }
        }
    }
    k=0;\/\/3顺子的长度
    for(int i=3;i<=14;i++){
        if(t[i]<=2) k=0;
        else{
            k++;
            if(k>=2){
                for(int j=i-k+1;j<=i;j++) t[j]-=3;
                dfs(x+1);
                for(int j=i-k+1;j<=i;j++) t[j]+=3;
            }
        }
    }
    for(int i=3;i<=15;i++){
        if(t[i]>=3){
            t[i]-=3;
            for(int j=3;j<=16;j++){\/\/三带一
                if(t[j]>0&&i!=j){\/\/若i==j就等于炸弹
                    t[j]--;
                    dfs(x+1);
                    t[j]++;
                }
            }
            for(int j=3;j<=15;j++){\/\/三代二（王炸不是对牌）
                if(t[j]>=2&&i!=j){
                    t[j]-=2;
                    dfs(x+1);
                    t[j]+=2;
                }
            }
            t[i]+=3;
        }
        if(t[i]>=4){
            t[i]-=4;
            for(int j=3;j<=16;j++){\/\/4+2(单)
                if(t[j]>=1&&i!=j){
                    t[j]--;
                    for(int k=3;k<=16;k++){
                        if(t[k]>=1&&j!=k){
                            t[k]--;
                            dfs(x+1);
                            t[k]++;
                        }
                    }
                    t[j]++;
                }
            }
            for(int j=3;j<=15;j++){\/\/4+2（对子）
                if(t[j]>=2&&i!=j){
                    t[j]-=2;
                    for(int k=3;k<=15;k++){
                        if(t[k]>=2&&j!=k){
                            t[k]-=2;
                            dfs(x+1);
                            t[k]+=2;
                        }
                    }
                    t[j]+=2;
                }
            }
            t[i]+=4;
        }
    }
    for(int i=3;i<=16;i++){
        if(t[i]>0){
            x++;
        }
    }
    minn=min(minn,x);
}
signed main() {
    int T,n;
    cin>>T>>n;
    while(T--){
        memset(t,0,sizeof(t));
        minn=0x3f3f3f3f;
        for(int i=1;i<=n;i++){
            int x,y;
            cin>>x>>y;
            if(x==0) t[16]++;\/\/大小王
            else if(x==2) t[15]++;\/\/2
            else if(x==1) t[14]++;\/\/A
            else t[x]++;
        }
        dfs(0);
        cout<<minn<<endl;
    }

    return 0;
}