斗地主

天南子Arthur · 2019-11-07 22:04:55 · 个人记录

斗地主

• 题目描述

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中，牌的大小关 系根据牌的数码表示如下:

1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1

3

1 17
12 3
4 3
2 3
5 4
10 2
3 3
12 2
0 1
1 3
10 1
6 2
12 1
11 3
5 2
12 4
2 2
7 2

6

• 数据范围与规模

思路

需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下……

信你个鬼，你谷你个糟老头子坏得很，个人感觉与我平时打的斗地主没有什么区别，感觉就引诱你再次认真读一遍早就已经理解的题，然后浪费时间……

然后就是个大暴搜

枚举所有情况，最后取一个MAX

注意一下顺子和三带X和四带2

然后貌似大小王可以被三带或者四带

注意细节

不要调崩溃

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int ki[20],n,minn,q;
int calc()
{
    int res=0;
    for(int i=2;i<=16;++i)
    {
        if(ki[i]==4)res++;
        if(ki[i]==3)res++;
        if(ki[i]==2)res++;
        if(ki[i]==1)res++;
    }
    return res;
}
void dfs(int dep,int ans)
{
    if(ans>minn)return;
    if(dep==n){minn=ans;return;}
    int tot=calc();
    if(tot+ans<minn)minn=tot+ans;
    for(int i=2;i<=16;++i)
    {
        if(ki[i]==4)
        {
            for(int j=2;j<=15;++j)if(ki[j]>=2&&i!=j)
                for(int k=j;k<=16;++k)if(ki[k]>=2&&i!=k&&k!=j)
                {
                    ki[i]-=4,ki[j]-=2,ki[k]-=2;
                    dfs(dep+8,ans+1);
                    ki[i]+=4,ki[j]+=2,ki[k]+=2;
                }
            for(int j=2;j<=15;++j)if(ki[j]>=1&&i!=j)
                for(int k=j;k<=16;++k)if(ki[k]>=1&&i!=k&&k!=j)
                {
                    ki[i]-=4,ki[j]-=1,ki[k]-=1;
                    dfs(dep+6,ans+1);
                    ki[i]+=4,ki[j]+=1,ki[k]+=1;
                }
        }
        if(ki[i]>=3)
        {
            int sum=1;
            for(int j=i+1;j<=14;++j)
                if(ki[j]>=3)sum++;
                else break;
            if(sum>=2)
            {
                for(int j=i;j<=sum+i-1;++j)ki[j]-=3;
                dfs(dep+sum*3,ans+1);
                for(int j=i;j<=sum+i-1;++j)ki[j]+=3;
            }
            for(int j=2;j<=16;++j)if(ki[j]>=2&&i!=j)
            {
                ki[i]-=3,ki[j]-=2;
                dfs(dep+5,ans+1);
                ki[i]+=3,ki[j]+=2;
            }
            for(int j=2;j<=16;++j)if(ki[j]>=1&&i!=j)
            {
                ki[i]-=3,ki[j]-=1;
                dfs(dep+4,ans+1);
                ki[i]+=3,ki[j]+=1;
            }
        }
        if(ki[i]>=2)
        {
            if(i!=2)
            {
                int sum=1;
                for(int j=i+1;j<=14;++j)
                    if(ki[j]>=2)sum++;
                    else break;
                if(sum>=3)
                {
                    for(int j=i;j<=sum+i-1;++j)ki[j]-=2;
                    dfs(dep+sum*2,ans+1);
                    for(int j=i;j<=sum+i-1;++j)ki[j]+=2;
                }
            }
        }
        if(ki[i]>=1)
        {
            if(i>2&&i<11)
            {
                int sum=1;
                for(int j=i+1;j<=14;++j)
                    if(ki[j]>=1)sum++;
                    else break;
                if(sum>=5)
                {
                    for(int j=i;j<=i+sum-1;++j)ki[j]-=1;
                    dfs(dep+sum,ans+1);
                    for(int j=i;j<=i+sum-1;++j)ki[j]+=1;
                }
                if(i==15&&ki[16]>=1)
                {
                    ki[15]-=1,ki[16]-=1;
                    dfs(dep+2,ans+1);
                    ki[15]+=1,ki[16]+=1;
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&q,&n);
    while(q--)
    {
        for(int i=1;i<=19;++i)ki[i]=0;minn=127;
        for(int tmp,tmp1,i=1;i<=n;++i)
        {
            scanf("%d%d",&tmp,&tmp1);
            if(!tmp)
            {
                if(tmp1==1)ki[15]++;
                else ki[16]++;continue;
            }
            if(tmp==1)tmp=14;
            ki[tmp]++;
        }
        dfs(0,0);
        printf("%d\n",minn);
    }
    return 0;
}