记录编号	458471	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]斗地主	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2017-10-11 14:22:05	内存使用	0.31 MiB

#include<bits/stdc++.h>//如果不出顺子，那么我们出完牌所需的步数是一定的 
using namespace std;//我们将每种牌按其的个数分为若干组，每一组都可以自己单独打出,那么我么需要尽可能合并这些组(4+2,3+1……) 
//通常是不拆牌的，4个的3个的拆了肯定不会更优(无顺子)，但有一种情况特殊，一炸弹一对一单，这种情况下需要拆开对 
int T,n,num[24],cnt[20],mi,ans[5];
int get(){
	memset(ans,0,sizeof(ans));int tem=0;
	for(int i=3;i<=16;i++)ans[cnt[i]]++;
	while(ans[4]>=1&&ans[2]>=2)ans[4]--,ans[2]-=2,tem++;
	while(ans[4]>=1&&ans[1]>=2)ans[4]--,ans[1]-=2,tem++;
	if(ans[4]>=1&&ans[2]==1&&ans[1]==1)ans[4]--,ans[2]--,tem++;
	while(ans[3]>=1&&ans[2]>=1)ans[3]--,ans[2]--,tem++;
	while(ans[3]>=1&&ans[1]>=1)ans[3]--,ans[1]--,tem++;
	return tem+ans[1]+ans[2]+ans[3]+ans[4];
}
void dfs(int x){
	mi=min(mi,get()+x);
	for(int i=3;i<=13;i++){
		int j=i;while(cnt[j]>=3&&j<=14)j++;
		if(j-i<2)continue;
		for(int l=2;l<=j-i;l++){
			for(int k=i;k<=i+l-1;k++){
				cnt[k]-=3;
			}dfs(x+1);
			for(int k=i;k<=i+l-1;k++)cnt[k]+=3;
		}
	}
	for(int i=3;i<=12;i++){
		int j=i;while(cnt[j]>=2&&j<=14)j++;
		if(j-i<3)continue;
		for(int l=3;l<=j-i;l++){
			for(int k=i;k<=i+l-1;k++){
				cnt[k]-=2;
			}dfs(x+1);
			for(int k=i;k<=i+l-1;k++)cnt[k]+=2;
		}
	}
	for(int i=3;i<=10;i++){
		int j=i;while(cnt[j]&&j<=14)j++;//不能跟2组 
		if(j-i<5)continue;
		for(int l=5;l<=j-i;l++){
			for(int k=i;k<=i+l-1;k++){
				cnt[k]--;
			}dfs(x+1);
			for(int k=i;k<=i+l-1;k++)cnt[k]++;
		}
	}
}
int main()
{
	freopen("landlords.in","r",stdin);freopen("landlords.out","w",stdout);
	scanf("%d%d",&T,&n);int tot=0;
	while(T--){
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++){
			int x,y;scanf("%d%d",&x,&y);num[i]=x;
			if(x==0)num[i]=16;if(x==1)num[i]=14;
			if(x==2)num[i]=15;cnt[num[i]]++;
		}mi=0x3fffffff;tot++;
		dfs(0);cout<<mi<<endl;
	}
	return 0;
}