斗地主题解

__S08577__ · 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;
}

斗地主题解

整个DFS都别忘了回溯。