记录编号	279179	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]斗地主	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-07-08 20:57:11	内存使用	0.00 MiB

#include<stdio.h>
#include<string.h>
#define Min(a,b) (a)<(b)?(a):(b)
#define D 14
inline void read(int &x)
{
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9');
	x=ch-'0';
	while(ch=getchar(),ch>47&&ch<58)x=(x<<3)+(x<<1)+ch-'0';
}
int a[20]={0},b[5]={0},ans=0;
inline int search(int x[])
{
	memset(b,0,sizeof(b));
	int i,s=0;
	for(i=3;i<D+3;i++) b[x[i]]++;
	while(b[4]&&b[2]>=2) s++,b[4]--,b[2]-=2;
	while(b[4]&&b[1]>=2) s++,b[4]--,b[1]-=2;
	while(b[3]&&b[2]>=1) s++,b[3]--,b[2]--;
	while(b[3]&&b[1]>=1) s++,b[3]--,b[1]--;
	return s+b[1]+b[2]+b[3]+b[4];
}
inline void dfs(int deep,int rest[])
{
	if(deep>ans) return;
	ans=Min(ans,deep+search(rest));
	int i,j,k,l;
	for(i=3;i<=D-1;i++){
		for(j=i;rest[j]>=3&&j<=D;j++);
		if(j-i>=2){
			for(k=j;k-i>=2;k--){
				for(l=i;l<k;l++) rest[l]-=3;
				dfs(deep+1,rest);
				for(l=i;l<k;l++) rest[l]+=3;
			}
		}
	}
	for(i=3;i<=D-2;i++){
		for(j=i;rest[j]>=2&&j<=D;j++);
		if(j-i>=3){
			for(k=j;k-i>=3;k--){
				for(l=i;l<k;l++) rest[l]-=2;
				dfs(deep+1,rest);
				for(l=i;l<k;l++) rest[l]+=2;
			}
		}
	}
	for(i=3;i<=D-4;i++){
		for(j=i;rest[j]>=1&&j<=D;j++);
		if(j-i>=5){
			for(k=j;k-i>=5;k--){
				for(l=i;l<k;l++) rest[l]-=1;
				dfs(deep+1,rest);
				for(l=i;l<k;l++) rest[l]+=1;
			}
		}
	}
}
int _521()
{
	freopen("landlords.in","r",stdin);
	freopen("landlords.out","w",stdout);
	int T,n;
	read(T),read(n);
	while(T--){
		memset(a,0,sizeof(a));
		for(int i=1,j,k;i<=n;i++){
			read(j);read(k);
			if(j==0) j=16;
			else if(j<3) j+=13;
			a[j]++;
		}
		ans=search(a);
		dfs(0,a);
		printf("%d\n",ans);
	}
	return 0;
}
int _520=_521();
int main(){;}