记录编号	430935	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]斗地主	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2017-07-30 20:45:14	内存使用	0.31 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

int n;
int ans;
int sum[20];
int cnt[10];

int MakePair();
void DFS(int);
void Initialize();
int Convert(int);

int main(){
	freopen("landlords.in","r",stdin);
	freopen("landlords.out","w",stdout);
	int t;
	scanf("%d%d",&t,&n);
	while(t--){
		Initialize();
		ans=MakePair();
		DFS(0);
		printf("%d\n",ans);
	}
}

void Initialize(){
	int x,trash;
	memset(sum,0,sizeof(sum));
	for(int i=0;i<n;i++){
		scanf("%d%d",&x,&trash);
		sum[Convert(x)]++;
	}
}

int MakePair(){
	memset(cnt,0,sizeof(cnt));
	int ans=0;
	for(int i=1;i<=14;i++)
		cnt[sum[i]]++;
	while(cnt[4]>=1&&cnt[2]>=2){
		cnt[4]--;
		cnt[2]-=2;
		ans++;
	}
	while(cnt[4]>=1&&cnt[1]>=2){
		cnt[4]--;
		cnt[1]-=2;
		ans++;
	}
	while(cnt[3]>=1&&cnt[2]>=1){
		cnt[3]--;
		cnt[2]--;
		ans++;
	}
	while(cnt[3]>=1&&cnt[1]>=1){
		cnt[3]--;
		cnt[1]--;
		ans++;
	}
	ans+=cnt[1]+cnt[2]+cnt[3]+cnt[4];
	return ans;
}

void DFS(int deep){
	if(deep>ans)
		return;
	ans=std::min(ans,deep+MakePair());
	for(int i=1;i<=11;i++){
		int tmp=i;
		while(tmp<=12&&sum[tmp]>=3)
			tmp++;
		tmp--;
		if(tmp-i+1<2)
			continue;
		for(int k=tmp;k-i+1>=2;k--){
			for(int j=i;j<=k;j++)
				sum[j]-=3;
			DFS(deep+1);
			for(int j=i;j<=k;j++)
				sum[j]+=3;
		}
	}
	for(int i=1;i<=10;i++){
		int tmp=i;
		while(tmp<=12&&sum[tmp]>=2)
			tmp++;
		tmp--;
		if(tmp-i+1<3)
			continue;
		for(int k=tmp;k-i+1>=3;k--){
			for(int j=i;j<=k;j++)
				sum[j]-=2;
			DFS(deep+1);
			for(int j=i;j<=k;j++)
				sum[j]+=2;
		}
	}
	for(int i=1;i<=8;i++){
		int tmp=i;
		while(tmp<=12&&sum[tmp]>=1)
			tmp++;
		tmp--;
		if(tmp-i+1<5)
			continue;
		for(int k=tmp;k-i+1>=5;k--){
			for(int j=i;j<=k;j++)
				sum[j]--;
			DFS(deep+1);
			for(int j=i;j<=k;j++)
				sum[j]++;
		}
	}
}

inline int Convert(int x){
	if(x==0)
		return 14;
	else if(x==2)
		return 13;
	else if(x==1)
		return 12;
	else
		return x-2;
}