记录编号	327383	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]斗地主	最终得分	100
用户昵称	浮生随想	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2016-10-21 21:48:19	内存使用	0.31 MiB

/*
在第一眼看到这道题的时候，马上的感觉就是复杂。情况种类太多以至于貌似无法分类，从而导致无从下手的状态。
但是，我们仔细回想一下问题所在，出牌的主要特征有两种，一种是顺子，一种是重复牌。
对于重复牌，有两种主要的出法：第一，直接出牌，第二，带着一些其他的牌。
那么，我们可以考虑将重复牌和顺子分类进行处理。
对于每一种牌的个数预处理出来，把牌的优先级简化一下，变成1~14（注意这里大小王不能区分开！因为大小王可以组成对子，他们两个是没有优先级的区别的！）
深搜查找情况，在深搜中进行对顺子的枚举的处理，我们知道，对于每一个不同的顺子形成的状态，都有一个最少操作数的重复牌的操作和它相互满足。
即，顺子和对子的操作数加起来。正好能将所有的牌都出完。
深搜中枚举可行的顺子，然后在每一次深搜的时候，处理出了这些顺子之后对应的重复牌的情况，相加，即为当前操作数的总和。
另外，附带一句，对于重复牌的操作，一个单牌也算在重复牌操作中。
**/ 
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define maxn 30
int a[maxn],n,ans;
int getval(int x,int y){
	int tem=0;
	if(x==1)tem=12;
	else if(x==2)tem=13;
	else if(x==0)tem=14;
	else if(x>=3&&x<=13)tem=x-2;
	return tem;
}
int search(){
	int tem=0;
	int b[6]={0};
	for(int i=1;i<=15;i++)b[a[i]]++;
	while(b[4]&&b[2]>=2)tem++,b[4]--,b[2]-=2;//四带二对； 
	while(b[4]&&b[1]>=2)tem++,b[4]--,b[1]-=2;//四带二单；
	while(b[3]&&b[2]>=1)tem++,b[3]--,b[2]--;//三带二； 
	while(b[3]&&b[1]>=1)tem++,b[3]--,b[1]--;//三带一； 
	tem+=b[1]+b[2]+b[3]+b[4];
	//cout<<tem<<endl;
	return tem;//把带的情况去除了之后，剩下仍然不能凑成一种输出 
}
void dfs(int num){
	if(num>ans)return;
	int x=search();
	//cout<<num<<" "<<x<<endl;
	ans=min(ans,num+x);
	for(int i=1;i<=11;i++){//三顺子 
		int j;
		for(j=i;a[j]>=3&&j<=12;j++);
		if(j-i<2)continue;
		//cout<<"hehe"<<i<<" "<<j<<endl;
		for(int k=j;k-i>=2;k--){//注意这里是错点！！
		//当有一个很大的顺子的时候，我们未必选取最大的顺子是最优!
		//也就是说，这个顺子每一段的长度我都至少要枚举一边。
		//之前想的简单了，以为只要把最大的顺子放上就可以了，然而这样只有60分； 
		//改正之后可过。 
			for(int l=i;l<k;l++)a[l]-=3;
			dfs(num+1);
			for(int l=i;l<k;l++)a[l]+=3;
		}		
	}
	for(int i=1;i<=10;i++){//对顺子 
		int j;
		for(j=i;a[j]>=2&&j<=12;j++);
		if(j-i<3)continue;
		for(int k=j;k-i>=3;k--){
			for(int l=i;l<k;l++)a[l]-=2;
			dfs(num+1);
			for(int l=i;l<k;l++)a[l]+=2;
		}		
	}
	for(int i=1;i<=8;i++){//单顺子 
		int j;
		for(j=i;a[j]>=1&&j<=12;j++);
		if(j-i<5)continue;
		for(int k=j;k-i>=5;k--){
			for(int l=i;l<k;l++)a[l]-=1;
			dfs(num+1);
			for(int l=i;l<k;l++)a[l]+=1;
		}		
	}
}	 
int main(){
	freopen("landlords.in","r",stdin);
	freopen("landlords.out","w",stdout);
	int t;
	scanf("%d%d",&t,&n);
	while(t--){
		ans=0x7f7f7f7f; 
		memset(a,0,sizeof a);
		for(int i=1;i<=n;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			int z=getval(x,y);
			a[z]++;
		}
		ans=search();
		dfs(0);
		printf("%d\n",ans);
	}
	//while(1);
}