NOIP2015 斗地主

NOIP2015 斗地主

传送门

Description

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、 方片的 A 到 K 加上大小王的共 54 张牌来进行的扑克牌游戏。在斗地主中,牌的大小关
系根据牌的数码表示如下:3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王,而花色并不对牌的大小产生影响。每一局游戏中,一副手牌由 n 张牌组成。游戏者每次可以根据规定的牌型进行出牌,首先打光自己的手牌一方取得游戏的胜利。
现在,牛牛只想知道,对于自己的若干组手牌,分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。
需要注意的是,本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。
具体规则如下:

伪·斗地主规则

Solution

暴力搜索就行了
注意一下dfs枚举的顺序,先顺子,再四带二(两对),再三带一(一对),最后,相同种类的牌一起出就可以了。

开始看着挺吓人的,其实写起来还是挺好写。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int T,n;
int cnt[17],ans=99;
const int size[4]={0,5,3,2};
void dfs(int x)
{
    if(x>ans) return;
    for(int i=3;i;i--)//处理顺子,i是顺子中相同牌的个数
    {
        int l=0;
        for(int j=3;j<=14;j++)
        {
            if(cnt[j]>=i) l++;else l=0;
            if(l>=size[i])
            {
                for(int k=j-l+1;k<=j;k++) cnt[k]-=i;
                dfs(x+1);
                for(int k=j-l+1;k<=j;k++) cnt[k]+=i;
            }
        }
    }
    for(int i=2;i<=14;i++)//处理4带2,注意处理4带两对
    {
        if(cnt[i]>=4)
        {
            cnt[i]-=4;
            for(int j=2;j<=14;j++)
            {
                if(i==j||cnt[j]<2) continue;
                cnt[j]-=2;
                for(int k=2;k<=14;k++) 
                {
                    if(cnt[k]<2||k==j) continue;
                    cnt[k]-=2;dfs(x+1);cnt[k]+=2; 
                }
                cnt[j]+=2;
            }
            for(int j=2;j<=15;j++)
            {
                if(i==j||cnt[j]<1) continue;
                --cnt[j];
                for(int k=2;k<=15;k++)
                {
                    if(cnt[k]<1||k==j) continue;
                    --cnt[k];dfs(x+1);++cnt[k];
                }
                ++cnt[j];
            }
            cnt[i]+=4;
        }
    }
    for(int i=2;i<=14;i++)//处理3带(1\2)
    {
        if(cnt[i]>=3)//3带2
        {
            cnt[i]-=3;
            for(int j=2;j<=14;j++)
            {
                if(cnt[j]<2||i==j) continue;
                cnt[j]-=2;
                dfs(x+1);
                cnt[j]+=2;
            }
            for(int j=2;j<=15;j++)//3带1
            {
                if(cnt[j]<1||i==j) continue;
                --cnt[j];dfs(x+1);++cnt[j];
            }
            cnt[i]+=3;
        }
    }
    for(int i=2;i<=15;i++) if(cnt[i]>0) ++x;//剩下的牌只能每种相同的牌单独出,每种牌只用出一次
    ans=min(ans,x);
}
int main()
{
    T=read(),n=read();
    while(T--)
    {
        memset(cnt,0,sizeof(cnt));
        ans=99;
        for(int i=1;i<=n;i++){int x=read();if(x!=0)cnt[x]++;else cnt[15]++;x=read();}
        cnt[14]=cnt[1];dfs(0);printf("%d\n",ans);   
    }
    return 0;
}