记录编号	330018	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]斗地主	最终得分	100
用户昵称	残星誓言	是否通过	通过
代码语言	C++	运行时间	0.493 s
提交时间	2016-10-25 21:00:24	内存使用	0.20 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=20;
int n=15;
int th;int ans=2147483647;
int card[maxn];
int used[maxn];
/*
枚举顺序
	三顺子
	二顺子
	顺子
	four
	three 
	two
	one 
	ps 王不能顺子 或带出去
	wei chi dan zhang shu liang*/
int m;
bool find_one(bool flag)
{
	int tp;
	if(flag) tp=n; else tp=n-1; 
	for(int i=1;i<=tp;i++)
		if(card[i]-used[i]==1)
		{
			used[i]+=1;th=i;
			return true;
		}
		return false;
}
bool find_two(bool flag)
{	
	int tp;
	if(flag) tp=n; else tp=n-1;
	for(int i=1;i<=tp;i++)
		if(card[i]-used[i]>=2)
		{
			used[i]+=2;th=i;
			return true;
		}
		return false;
};
bool find_three()
{
	for(int i=1;i<=n;i++)
	{	
		if(card[i]-used[i]>=3)
		{
			used[i]+=3;th=i;
			return true;
		}
	
	}
	return false;
}
bool find_four()
{
	for(int i=1;i<=n;i++)
	{	
		if(card[i]-used[i]>=4)
		{
			used[i]+=4;th=i;  //printf("\nfind four=%d\n",i);
			return true;
		}
		
	}
	return false;
}
int  find_oneshunzi(int s)  //from s de shun zi chang du;
{
	int x=0;
	for(int i=s;i<n;i++)
		{
			if(card[i]-used[i]>=1)
			{
				x++;
			}
			else
			return x;
		}
	return x;
}
int  find_twoshunzi(int s)//from s de shun zi chang du;
{
	int x=0;
	for(int i=s;i<n;i++)
		{
			if(card[i]-used[i]>=2)
			{
				x++;
			}
			else
			return x;
		}
	return x;
}
int  find_threeshunzi(int s)  //from s de shun zi chang du;
{
	int x=0;
	for(int i=s;i<n;i++)
		{
			if(card[i]-used[i]>=3)
			{
				x++;
			}
			else
			return x;
		}
	return x;
}
void dfs(int X,int last)
{
		
/*	printf("\nx=%5d  last=%3d:\n",X,last);
	for(int i=1;i<=15;i++) printf("%3d ",i); putchar('\n');
	for(int i=1;i<=15;i++) printf("%3d ",card[i]-used[i]);*/
		if(X>=ans) return;
		if(last==0) {	ans=X;/*puts("233orz");*/return; }
		for(int i=3;i<=n;i++)
		{
			int x=find_oneshunzi(i); //printf("--%d--",x);
			if(x>=5)
			{	int s=i;
				for(int j=s;j<s+4;j++) used[j]++;
				for(int k=4;k<x;k++)
				{
					used[s+k]++;//puts("顺子");
					dfs(X+1,last-(k+1)); 
				}
				for(int k=i;k<i+x;k++) used[k]--;	
			}			
		}
		for(int i=3;i<=n;i++)
		{
			int x=find_twoshunzi(i);
			if(x>=3)
			{	int s=i;
				for(int j=s;j<s+2;j++) used[j]+=2;
				for(int k=2;k<x;k++)
				{
					used[s+k]+=2;//puts("二_顺子");
					dfs(X+1,last-(k+1)*2);
				}
				for(int k=i;k<i+x;k++) used[k]-=2;	
			}			
		}
		for(int i=3;i<=n;i++)
		{
			int x=find_threeshunzi(i);
			if(x>=2)
			{	int s=i;
				for(int j=s;j<s+1;j++) used[j]+=3;
				for(int k=1;k<x;k++)
				{
					used[s+k]+=3;//puts("三_顺子");
					dfs(X+1,last-(k+1)*3);
				}
				for(int k=i;k<i+x;k++) used[k]-=3;	
			}			
		}
		if(find_four())
		{
			int f=th;
			if(find_two(0))
			{
				int ff=th;
				if(find_two(0))
				{
					int fff=th;   //puts("4 dai 2 dui");
					dfs(X+1,last-8);
					used[fff]-=2;
				}
				used[ff]-=2;
			}
			if(find_one(1))
			{
				int ff=th;
				if(find_one(1))
				{
					int fff=th;	//puts("4 dai 2");
					dfs(X+1,last-6);
					used[fff]-=1;
				}
				used[ff]-=1;
			}
								//puts("炸弹");
			dfs(X+1,last-4);
			used[f]-=4;
			
		}
		if(find_three())
		{
			int f=th;
			if(find_two(0))
			{
				int ff=th;		//puts("三带一对");
				dfs(X+1,last-5);
				used[ff]-=2;
			}
			if(find_one(1))
			{
				int ff=th;		//puts("三带一");
				dfs(X+1,last-4);
				used[ff]-=1;
				
			}
			dfs(X+1,last-3);
			used[f]-=3;
		}
		if(find_two(1))
		{	int f=th;				//puts("对子");
			dfs(X+1,last-2);	
			used[f]-=2;
		}
		
		if(find_one(1))
		{	int f=th;						//puts("单张");
			dfs(X+1,last-1);
			used[f]-=1;     	//printf("|%d=%d|",th,used[th]);
		}
		
}
int main()
{	
	freopen("landlords.in","r",stdin);
	freopen("landlords.out","w",stdout);
	
	int t;
	scanf("%d%d",&t,&m);
	for(int cl=1;cl<=t;cl++)
	
	{
	memset(card,0,sizeof(card));
	memset(used,0,sizeof(used));
	ans=2147483647;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		if(a==1) card[14]++;
		else
		if(a==0) card[15]++;
		else
		card[a]++;
	}
	dfs(0,m);
	printf("%d\n",ans);

	}
	return 0;
}