斗地主

· · 题解

题目描述:

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、 方片的 A 到 K 加上大小王的共 54 张牌来进行的扑克牌游戏。在斗地主中，牌的大小关 系根据牌的数码表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由 n 张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。

现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。

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

具体规则如下：

解:

模拟+爆搜:

如果每一步直接搜的话显然太慢了:

于是可以贪心搜顺子:

1.A可以接在K后,输入时直接把A接在K后; 大王小王当对出 然后把其他的位置减一下即可:

输入的时候这样乱搞: 

          int x=read(),y=read();
          if(x==1)x=13;
          else if(x)x--;
          card[x]++;

2.每次找可以形成顺子的位置,然后尝试把顺子给出出去

先搜三顺子,再搜双顺子,再搜单顺子

搜顺子的过程(以三顺子为例): 

int sanshunzi(int i)
{
    int p=i;
    while(card[p]>=3&&p<=13)p++;
    if(p-i>=2)return p;
    //返回可形成三顺子的末位置
    return 0;//没有就返回0
}

3.顺子出完了之后然后开一个桶,设计一个calc函数, 贪心出散牌即可:

能出炸就出炸,炸没了就出三带n:

具体就像这样:

int calc()
{
    memset(a,0,sizeof(a));
    //开一个桶,把不同的装进去
    for(int i=0;i<=13;i++)
    ++a[card[i]];
    int tot=0;
    while(a[4]&&a[2]>=2)--a[4],a[2]-=2,++tot;
    //4带2个对
    while(a[4]&&a[1]>=2)--a[4],a[1]-=2,++tot;
    //4带2张牌
    while(a[4]&&a[2])--a[4],--a[2],++tot;
    //4带一个对
    while(a[3]&&a[2])--a[3],--a[2],++tot;
    //3带2
    while(a[3]&&a[1])--a[3],--a[1],++tot;
    //3带一
    return tot+a[1]+a[2]+a[3]+a[4];
    //不能带的直接出出去
}

4.最后dfs,答案即为打顺子步数+贪心出散牌步数.

注意:一定要注意多组数据!!!!!

(样例很坑)

完整代码:

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int n,t;
int a[21],card[21],ans=31;

inline int read()
{
    int X=0,w=0;char ch=0;
    while(!isdigit(ch))
    {
        w|=ch=='-';ch=getchar();
    }
    while(isdigit(ch))
    {
        X=X*10+ch-'0';ch=getchar();
    }
    return w?-X:X;
}

int danshunzi(int i)
{
    int p=i;
    while(card[p]>=1&&p<=13)p++;
    if(p-i>=5)return p;
    return 0;
}

int shuangshunzi(int i)
{
    int p=i;
    while(card[p]>=2&&p<=13)p++;
    if(p-i>=3)return p;
    return 0; 
}

int sanshunzi(int i)
{
    int p=i;
    while(card[p]>=3&&p<=13)p++;
    if(p-i>=2)return p;
    //返回可形成三顺子的末位置
    return 0;//没有就返回0
}

int calc()
{
    memset(a,0,sizeof(a));
    //开一个桶,把不同的装进去
    for(int i=0;i<=13;i++)
    ++a[card[i]];
    int tot=0;
    while(a[4]&&a[2]>=2)--a[4],a[2]-=2,++tot;
    //4带2个对
    while(a[4]&&a[1]>=2)--a[4],a[1]-=2,++tot;
    //4带2张牌
    while(a[4]&&a[2])--a[4],--a[2],++tot;
    //4带一个对
    while(a[3]&&a[2])--a[3],--a[2],++tot;
    //3带2
    while(a[3]&&a[1])--a[3],--a[1],++tot;
    //3带一
    return tot+a[1]+a[2]+a[3]+a[4];
    //不能带的直接出出去
}

void dfs(int step)
{
    if(step>=ans)return;//最优性剪枝 
    int k=calc();//贪心出散牌的步数 
    ans=min(ans,step+k);
    int pos;
    for(int i=2;i<=13;i++)
    {
        if(sanshunzi(i))//3顺子 
        {
            pos=sanshunzi(i);
            for(int j=i+1;j<=pos-1;j++)
            {
                for(int v=i;v<=j;v++)
                card[v]-=3;//枚举顺子 
                dfs(step+1);
                for(int v=i;v<=j;v++)
                card[v]+=3;//回溯 
            }
        }
    }
    for(int i=2;i<=13;i++)
    {
        if(shuangshunzi(i))//双顺子 
        {
            pos=shuangshunzi(i);
            for(int j=i+2;j<=pos-1;j++)
            {
                for(int v=i;v<=j;v++)
                card[v]-=2;
                dfs(step+1);
                for(int v=i;v<=j;v++)
                card[v]+=2;
            }
        }
    }
    for(int i=2;i<=13;i++)
    {
        if(danshunzi(i))//单顺子 
        {
            pos=danshunzi(i);
            for(int j=i+4;j<=pos-1;j++)
            {
                for(int v=i;v<=j;v++)
                card[v]--;
                dfs(step+1);
                for(int v=i;v<=j;v++)
                card[v]++;
            }
        }
    }
}

int main()
{
    cin>>t>>n;
    while(t--)
    {
        int x,y;
        ans=31;
        memset(card,0,sizeof(card));
        for(int i=1;i<=n;i++)
        {
          int x=read(),y=read();
          if(x==1)x=13;//输入时乱搞一下 
          else if(x)x--;
          card[x]++;
        }
         dfs(0);
         printf("%d\n",ans);
    }
}