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

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define N 35
using namespace std;
int a[N],num[N],n,T,ANS;
void read(){
	int x,nouse;
	memset(a,0,sizeof a);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x,&nouse);
		if(x==1) a[12]++; if(x==2) a[13]++;
		if(x==0) a[14]++; if(x>=3) a[x-2]++;
	}
}
int no_str(){
	memset(num,0,sizeof num); int tot=0;
	for(int i=1;i<=14;i++) num[a[i]]++;
	while(num[4]&&num[2]>=2)num[4]--,num[2]-=2,tot++;
	while(num[4]&&num[1]>=2)num[4]--,num[1]-=2,tot++;
	while(num[3]&&num[2])num[3]--,num[2]--,tot++;
	while(num[3]&&num[1])num[3]--,num[1]--,tot++;
	return tot+num[1]+num[2]+num[3]+num[4];
}
void dfs(int step){
	if(step>ANS) return;
	ANS=min(ANS,step+no_str());
	for(int i=1;i<=11;i++){
		int ii=i;
		while(ii<=12&&a[ii]>=3)ii++;ii--;
		if(ii-i+1<2) continue;
		for(;ii-i+1>=2;ii--){
			for(int j=i;j<=ii;j++) a[j]-=3;
			dfs(step+1);
			for(int j=i;j<=ii;j++) a[j]+=3;
		}
	}
	for(int i=1;i<=10;i++){
		int ii=i;
		while(ii<=12&&a[ii]>=2)ii++;ii--;
		if(ii-i+1<3) continue;
		for(;ii-i+1>=3;ii--){
			for(int j=i;j<=ii;j++) a[j]-=2;
			dfs(step+1);
			for(int j=i;j<=ii;j++) a[j]+=2;
		}
	}
	for(int i=1;i<=8;i++){
		int ii=i;
		while(ii<=12&&a[ii])ii++;ii--;
		if(ii-i+1<5) continue;
		for(;ii-i+1>=5;ii--){
			for(int j=i;j<=ii;j++) a[j]--;
			dfs(step+1);
			for(int j=i;j<=ii;j++) a[j]++;
		}
	}
}
int gy()
{
	freopen("landlords.in","r",stdin);
	freopen("landlords.out","w",stdout);
	scanf("%d%d",&T,&n);
	while(T--){
		read();
		ANS=no_str();
		dfs(0);
		printf("%d\n",ANS);
	}
}
int ryf=gy();
int main(){;}