[NOIP2015]斗地主

自行脑补欢乐斗地主BGM

题目(洛谷)
先说下……这题在vijos上有个测试点错误,所以我就贴洛谷的链接了。
来说下这题吧,首先应该知道这肯定是一道搜索题。
对于这道题,我们要设计一个函数h(),这不是乐观估价函数,只是个用于计算当前手牌最少需要多少次出完。
对于这个h(),要注意:能4带2就4带2,然后再4带1,再3带2…….依此类推,这样能保证次数最少。
然后就是这个dfs了……
注意顺子分三种:单顺子,双顺子,三顺子。
从顺子进行深度搜索:有顺子就出,然后看剩下手牌需要多少次,更新ans。
如果当前答案大于ans,剪枝。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[25],c[5];
int t,n;
int ans;
int h()
{
	memset(c,0,sizeof c);
	for (int i=0;i<=13;++i)
		c[a[i]]++;
	int tmp=0;
	while (c[4] && c[2]>=2)
	//四带两对
	{
		c[4]--;
		c[2]-=2;
		tmp++;
	}
	while (c[4] && c[1]>=2)
	//四带两张单牌
	{
		c[4]--;
		c[1]-=2;
		tmp++;
	}
	while (c[4] && c[2])
	//四带一对
	{
		c[4]--;
		c[2]--;
		tmp++;
	}
	while (c[3] && c[2])
	//三带一对
	{
		c[3]--;
		c[2]--;
		tmp++;
	}
	while (c[3] && c[1])
	//三带一张单牌
	{
		c[3]--;
		c[1]--;
		tmp++;
	}
	//剩下的牌
	return tmp+c[1]+c[2]+c[3]+c[4];
}
void dfs(int step)
{
	if (step>=ans) return;
	int tmp=h();
	ans=min(ans,tmp+step);
	for (int i=2;i<=13;++i)
	{
		int j=i;
		while (a[j]>=3) ++j;
		if (j-i>=2)
		{
			for (int k=i+1;k<=j-1;++k)
			{
				for (int p=i;p<=k;++p) a[p]-=3;
				dfs(step+1);
				for (int p=i;p<=k;++p) a[p]+=3;
			}
		}
	}
	for (int i=2;i<=13;++i)
	{
		int j=i;
		while (a[j]>=2) ++j;
		if (j-i>=3)
		{
			for (int k=i+2;k<=j-1;++k)
			{
				for (int p=i;p<=k;++p) a[p]-=2;
				dfs(step+1);
				for (int p=i;p<=k;++p) a[p]+=2;
			}
		}
	}
	for (int i=2;i<=13;++i)
	{
		int j=i;
		while (a[j]>=1) ++j;
		if (j-i>=5)
		{
			for (int k=i+4;k<=j-1;++k)
			{
				for (int p=i;p<=k;++p) a[p]--;
				dfs(step+1);
				for (int p=i;p<=k;++p) a[p]++;
			}
		}
	}
}
int main()
{
	scanf("%d",&t);
	scanf("%d",&n);
	while (t--)
	{
		memset(a,0,sizeof a);
		int x,y;
		for (int i=1;i<=n;++i)
		{
			scanf("%d%d",&x,&y);
			if (x==1) x=13;
			else if (x) x--;
			a[x]++;
		}
		ans=999999999;
		dfs(0);
		printf("%d\n",ans);
	}
	return 0;
}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注