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

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
int t,n,ans=100000;
struct pai
{
	int f[20];
}a;
int read()
{
	int sum=0,f=1;char x=getchar();
	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
	while(x>='0'&&x<='9')sum=sum*10+x-'0',x=getchar();
	return sum*f;
}
int check(int x,pai b,int len)
{
	int s=0;
	for(int i=x;i<13;i++)
	   if(b.f[i]>=len)
	     s++;
	   else
	      break;
	return s;
}
void dfs(int len,pai x,int sum)
{
	if(len==0)
	{
		ans=min(ans,sum);
		return;
	}
	pai b=x;
	for(int i=1;i<13;i++)
	if(x.f[i]>0)
	{
	   int k=check(i,x,1);
	   if(k<5)continue;
	   for(int j=0;j<k;j++)
	       b.f[i+j]--;
	   // cout<<"shunzi"<<k<<" "<<i<<" "<<sum<<" "<<len<<endl;
	   dfs(len-k,b,sum+1);
	   b=x;
	}
	for(int i=1;i<13;i++)
	if(x.f[i]>1)
	{
	   int k=check(i,x,2);
	   if(k<3)continue;
	   for(int j=0;j<k;j++)
	       b.f[i+j]-=2;
	   dfs(len-k*2,b,sum+1);
	   b=x;
	}
	for(int i=1;i<13;i++)
	if(x.f[i]>2)
	{
	   int k=check(i,x,3);
	   if(k<3){
	      continue;
		}
	   for(int j=0;j<k;j++)
	       b.f[i+j]-=3;
	   dfs(len-k*3,b,sum+1);
	   b=x;
	}
	for(int i=0;i<13;i++)
	if(x.f[i]==4)
		for(int j1=0;j1<13;j1++)
	       if(j1!=i&&x.f[j1]>0)
	          for(int j2=0;j2<13;j2++)
	             if(j2!=i&&j2!=j1&&x.f[j2]>0)
	             {
	             	b.f[i]-=4;
	             	b.f[j1]--;b.f[j2]--;
	             	dfs(len-6,b,sum+1);
	             	b=x;
	             	if(b.f[j1]>=2&&b.f[j2]>=2)
	             	{
	             		b.f[i]-=4;
	             		b.f[j1]-=2;b.f[j2]-=2;
					    dfs(len-8,b,sum+1);
					    b=x;
					}
				 }
	for(int i=0;i<13;i++)
	if(x.f[i]>=3)
		for(int j1=0;j1<13;j1++)
	       if(j1!=i&&x.f[j1]>0)
           {
	         	b.f[i]-=3;
	         	b.f[j1]--;
	         	dfs(len-4,b,sum+1);
	         	b=x;
	         	if(b.f[j1]>=2)
	         	{
	         		b.f[i]-=3;
	         		b.f[j1]-=2;
				    dfs(len-5,b,sum+1);
				    b=x;
				}
		   }
	int w=0;
	//cout<<"dan"<<" ";
	for(int i=0;i<=13;i++)
	if(x.f[i]>0)
	{//cout<<i<<" ";
		b.f[i]=0;
		w++;
	}
//	cout<<endl<<w<<" "<<sum<<endl;
	dfs(0,b,sum+w);
	b=x;
}
int yjn()
{
	freopen("landlords.in","r",stdin);
	freopen("landlords.out","w",stdout);
    scanf("%d%d",&t,&n);
    while(t--)
    {
    	ans=1000000;
    	memset(a.f,0,sizeof(a.f));
    	for(int i=1;i<=n;i++)
    	{
    		int x;
    		scanf("%d",&x);
    		if(x==0)a.f[13]++;
			else
			{
				if(x==1)a.f[12]++;
				else a.f[x-2]++;
			}
			scanf("%d",&x);
		}
		dfs(n,a,0);
		printf("%d\n",ans);
	}
}
int qty=yjn();
int main(){;}