记录编号	207248	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]斗地主	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	0.613 s
提交时间	2015-11-12 09:09:17	内存使用	1.96 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int maxn=30;
const int inf=0x7fff;
 
int T,N;
int cnt[maxn],seq[maxn];
 
void init()
{
    memset(cnt,0,sizeof(cnt));
    memset(seq,0,sizeof(seq));
}
 
int search()
{
    if(N==2) {
        if(seq[0]==seq[1]) return 1;
        else return 2;
    }
    else if(N==3) {
        if(seq[0]==seq[1] && seq[1]==seq[2]) return 1;
        else if(seq[0]==seq[1] || seq[1]==seq[2]) return 2;
        else return 3;
    }
    else if(N==4) {
        if(cnt[seq[0]]==4) return 1;
        else if(cnt[seq[0]]==1 && cnt[seq[1]]==3) return 1;
        else if(cnt[seq[0]]==3 && cnt[seq[3]]==1) return 1;
        else if(cnt[seq[0]]==2 && cnt[seq[2]]==2) return 2;
        else if(seq[0]==seq[1] || seq[1]==seq[2] || seq[2]==seq[3])
            return 3;
        else return 4;
    }
    else {
        int ans=inf;
        int s1,s2,s3,t1,t2,t3;//顺子的首和尾
        s1=s2=s3=t1=t2=t3=3;
        bool finish=true;//牌是否出完
        //以下用14表示A，15表示2,16表示王
        for(int i=3;i<=16;i++) {
            if(cnt[i]) {
                finish=false;
                t1=i;
                if(t1-s1>=4 && i<15) {
                    for(int j=s1;j<=t1-4;j++)
                        for(int k=j+4;k<=t1;k++) {
                            for(int l=j;l<=k;l++) cnt[l]--;//出牌
                            ans=min(ans,search()+1);
                            for(int l=j;l<=k;l++) cnt[l]++;//回退
                        }//枚举顺子
                }
 
                if(cnt[i]>=2) {
                    t2=i;
                    if(t2-s2>=2 && i<15) {
                        for(int j=s2;j<=t2-2;j++)
                            for(int k=j+2;k<=t2;k++) {
                                for(int l=j;l<=k;l++) cnt[l]-=2;
                                ans=min(ans,search()+1);
                                for(int l=j;l<=k;l++) cnt[l]+=2;
                            }
                    }
                }
                else s2=i+1;
 
                if(cnt[i]>=3) {
                    t3=i;
                    if(t3-s3>=1 && i<15) {
                        for(int j=s3;j<=t3-1;j++)
                            for(int k=j+1;k<=t3;k++) {
                                for(int l=j;l<=k;l++) cnt[l]-=3;
                                ans=min(ans,search()+1);
                                for(int l=j;l<=k;l++) cnt[l]+=3;
                            }
                    }
                    cnt[i]-=3;
                    for(int j=3;j<=16;j++) {
                        if(cnt[j] && j!=i) {
                            cnt[j]--;
                            ans=min(ans,search()+1);
                            cnt[j]++;
                        }//三带一
                        if(cnt[j]>=2 && j<16) {
                            cnt[j]-=2;
                            ans=min(ans,search()+1);
                            cnt[j]+=2;//抱歉这里刚才有个手误（但愿考场上别写错吧）
                        }//三带二，带的两张牌不能是王（？）
                    }
                    cnt[i]+=3;
                }
                else s3=i+1;
 
                if(cnt[i]==4) {
                    cnt[i]-=4;
                    for(int j=3;j<=16;j++) 
                        if(cnt[j]>=2) {
                            cnt[j]-=2;
                            ans=min(ans,search()+1);
                            cnt[j]+=2;
                        }//四带两张单牌，带的单牌点数相等
                    for(int j=3;j<16;j++)
                        for(int k=j+1;k<=16;k++) {
                            if(cnt[j] && cnt[k]) {
                                cnt[j]--;
                                cnt[k]--;
                                ans=min(ans,search()+1);
                                cnt[j]++;
                                cnt[k]++;
                            }//四带二单
                            if(cnt[j]>=2 && cnt[k]>=2 && k<16) {
                                cnt[j]-=2;
                                cnt[k]-=2;
                                ans=min(ans,search()+1);
                                cnt[j]+=2;
                                cnt[k]+=2;
                            }//四带两对
                        }
                    cnt[i]+=4;
                }
            }
            else s1=s2=s3=i+1;
        }
 
        if(!finish) {
            int temp=0;
            for(int i=3;i<=16;i++) if(cnt[i]) temp++;
            ans=min(ans,temp);
        }//按点数处理完剩下的牌
        if(finish) return 0;//递归终止
        else return ans;
    }
 
    return 233;
}
 
int main()
{
	freopen("landlords.in", "r", stdin);
	freopen("landlords.out", "w", stdout);
    scanf("%d%d",&T,&N);
    while(T--) {
        init();
        for(int i=0;i<N;i++) {
            int v, t;scanf("%d %d",&v,&t);
            if(v==0) v=16;
            else if(v<3) v+=13;
            cnt[v]++;
            seq[i]=v;
        }
        sort(seq,seq+N);
        printf("%d\n",search());
    }
    return 0;
}