P2668 斗地主 (NOIP 提高 2015)

P2668

首先，如上图，我们有 三带一，三带二，单顺子，双顺子，三顺子和四带二 这几种特殊的牌型，在上图的牌型中，火箭也是比较特殊的，但是本题中只是需要两张鬼王牌即可，所以我们可以把火箭看为对子牌这种普通牌型

所以，我们只要在搜索的时候对于上面的几种特殊牌型进行特别的处理，最后剩下的手牌中每种相同点数的牌一定可以以单张牌，对子牌，三张牌和炸弹牌几种牌型打出

除此之外，还要注意每种牌型对于牌的特殊限制（如顺子中不能有 "2" 和鬼王），相应的对枚举的牌进行调整

---

源代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<algorithm>
#define ll long long
using namespace std;

const ll maxn=50;
ll T,n,ans,num,c;
ll vis[maxn];

inline void dfs(ll x)
{
	if(x>=ans) return ;//最优性剪枝
	
	ll len=0;
	
	for(int i=3;i<=14;i++)//单顺子
	{
		if(vis[i]==0) len=0;
		else
		{
			len++;
			if(len>=5)
			{
				for(int j=i;j>=i-len+1;j--) vis[j]--;
				dfs(x+1);
				for(int j=i;j>=i-len+1;j--) vis[j]++; 
			}
		}
	}
	
	len=0;
	
	for(int i=3;i<=14;i++)//双顺子
	{
		if(vis[i]<=1) len=0;
		else
		{
			len++;
			if(len>=3)
			{
				for(int j=i;j>=i-len+1;j--) vis[j]-=2;
				dfs(x+1);
				for(int j=i;j>=i-len+1;j--) vis[j]+=2;
			}
		}
	}
	
	len=0;
	
	for(int i=3;i<=14;i++)//三顺子
	{
		if(vis[i]<=2) len=0;
		else
		{
			len++;
			if(len>=2)
			{
				for(int j=i;j>=i-len+1;j--) vis[j]-=3;
				dfs(x+1);
				for(int j=i;j>=i-len+1;j--) vis[j]+=3;
			}
		}
	}
	
	for(int i=2;i<=14;i++)
	{
		if(vis[i]==3)
		{
			vis[i]-=3;
			for(int j=2;j<=15;j++)//三带一
			{
				if(vis[j]>=1&&j!=i)
				{
					vis[j]--;
					dfs(x+1);
					vis[j]++;
				}
			}
			for(int j=2;j<=14;j++)//三带二
			{
				if(vis[j]>=2&&j!=i)
				{
					vis[j]-=2;
					dfs(x+1);
					vis[j]+=2;
				}
			}
			vis[i]+=3;
		}
		else if(vis[i]==4)//有四张牌可以分为出三张留一张和全部都出
		{
			vis[i]-=3;
			
			for(int j=2;j<=15;j++)//三带一
			{
				if(vis[j]>=1&&j!=i)
				{
					vis[j]-=1;
					dfs(x+1);
					vis[j]+=1;
				}
			}
			
			for(int j=2;j<=14;j++)//三带二
			{
				if(vis[j]>=2&&j!=i)
				{
					vis[j]-=2;
					dfs(x+1);
					vis[j]+=2;
				}
			}
			
			vis[i]+=3;
			
			vis[i]-=4;
			
			for(int j=2;j<=15;j++)
			{
				if(vis[j]>=1&&j!=i)//四带两张
				{
					vis[j]--;
					
					for(int k=2;k<=15;k++)
					{
						if(vis[k]>=1&&j!=k)
						{
							vis[k]--;
							dfs(x+1);
							vis[k]++;
						}
					}
					
					vis[j]++;
				}
			}
			
			for(int j=2;j<=14;j++)//四带两对
			{
				if(vis[j]>=2&&j!=i)
				{
					vis[j]-=2;
					
					for(int k=2;k<=14;k++)
					{
						if(vis[k]>=2&&k!=j)
						{
							vis[k]-=2;
							dfs(x+1);
							vis[k]+=2;
						}
					}
					vis[j]+=2;
				}
			}
			
			vis[i]+=4;
		}
	}
	
	for(int i=2;i<=15;i++)//全部出完
	{
		if(vis[i]) x++;
	}
	
	ans=min(ans,x);
}

int main(void)
{
//	freopen("P2668_3.in","r",stdin);
//	freopen("z.out","w",stdout);
	
	scanf("%lld%lld",&T,&n);
	
	while(T--)
	{
		memset(vis,0,sizeof(vis));
		
		ans=9999999999;
	
		for(int i=1;i<=n;i++)//把牌按照大小以 3 为基准排好
		{
			scanf("%lld%lld",&num,&c);
			if(num==1) num=14;
			if(num==0) num=15;
			vis[num]++;
		}
		
		dfs(0);
		
//		if(ans==2) ans=3;
		
		printf("%lld
",ans);
	}
	
	return 0;
}