斗地主 题解

AC代码

（分析详见代码注释）

#include<bits/stdc++.h>
using namespace std;
int T,n,a[20],ans,kk;
void dfs(int sum)
{
	if(sum>ans) return;
	int bz=0;
	int k=0;
	for(int i=1;i<11;i++)
		if(a[i]>2&&a[i+1]>2&&a[i+2]>2)
		{
			k=i;
			while(a[k]>2&&k<13)
			{
				a[k]-=3,k++;
				if(k-i>2)
					dfs(sum+1);
			}
			for(int j=i;j<k;j++)
				a[j]+=3;
		}
	//判断三顺子（三顺子不一定要全出完，所以要边出边搜）
	for(int i=1;i<11;i++)
		if(a[i]>1&&a[i+1]>1&&a[i+2]>1)
		{
			k=i;
			while(a[k]>1&&k<13)
			{
				a[k]-=2,k++;
				if(k-i>2)
					dfs(sum+1);
			}
			for(int j=i;j<k;j++)
				a[j]+=2;
		}
	//判断二顺子 （同三顺子，边出边搜）
	for(int i=1;i<9;i++)
		if(a[i]&&a[i+1]&&a[i+2]&&a[i+3]&&a[i+4])
		{
			k=i;
			while(a[k]&&k<13)
			{
				a[k]--,k++;
				if(k-i>4)
					dfs(sum+1);
			}
			for(int j=i;j<k;j++)
				a[j]++;
		}
	//判断单顺子（同三顺子，边出边搜）
	int p1=0,p2=0,ss=0;
	for(int i=1;i<=14;i++)
		if(a[i]==1) p1++;
		else if(a[i]==2) p2++;
	//找出有多少张单牌 
    for(int i=1;i<14;i++)
    	if(a[i]==4)
    	{
    		if(p2>1) p2-=2;
    		else if(p1>1) p1-=2;
    		else if(p2) p2--;
    		ss++;
		}
	//判断四带，这时先把能带的二对先带完，在带一对，最后还剩就再把一对拆成两张带 
    for(int i=1;i<14;i++)
    	if(a[i]==3)
    	{
    		if(p1>0) p1--;
    		else if(p2>0) p2--;
    		ss++;
		}
	//判断三带，此时先带啥不重要
	ans=min(sum+p1+p2+ss,ans);
	//最后判断一张张一对对的出，然后记录
}
int main()
{
	scanf("%d%d",&T,&n);
	while(T--)
	{
		ans=9999999;
		for(int i=0;i<=15;i++) a[i]=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&kk);
			if(kk>2)	a[kk-2]++;
			else if(kk==0) a[14]++;
			else a[kk+11]++;
			scanf("%d",&kk);
		}
		dfs(0);
		printf("%d\n",ans);
	}
	return 0;
}