【BZOJ4325】【NOIP2015】斗地主搜索

题目描述

　　就是给你一副牌，问你最少几次能出完。

　　详细规则见规则

　　\(n\leq 23\)

题解

　　NOIP的数据非常水，错误一大堆的程序都能AC。

　　因为顺子对答案的影响最大，所以先枚举顺子进行搜索。

　　接下来网上很多的程序都直接计算答案了。实际上还要进行一次搜索，枚举拆牌的方案，有以下几种：

　　　1.一组四张牌可以拆成两组两张牌

　　　2.一组四张牌可以拆成一组一张牌+一组三张牌

　　　3.一组三张牌可以拆成一组一张牌+一组两张牌

　　　4.一组两张牌可以拆成两组一张牌

　　　5.一对王可以拆成两组一张牌

　　然后就可以计算方案。

　　加个最优性剪枝就可以过了。

　　时间复杂度：\(O(???)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

int s[20];

int a[20],c[20];

int ans,n;

int calc2()

{

	int res=0;

	memcpy(c,a,sizeof a);

	while(c[4]&&c[2]>=2)

	{

		c[4]--;

		c[2]-=2;

		res++;

	}

	while(c[4]&&c[1]>=2)

	{

		c[4]--;

		c[1]-=2;

		res++;

	}

	while(c[3]&&c[2])

	{

		c[3]--;

		c[2]--;

		res++;

	}

	while(c[3]&&c[1])

	{

		c[3]--;

		c[1]--;

		res++;

	}

	return res+c[1]+c[2]+c[3]+c[4];

}

int calc()

{

	int ans=calc2();

	if(a[4])

	{

		a[4]--;

		a[2]+=2;

		ans=min(ans,calc());

		a[4]++;

		a[2]-=2;

	}

	if(a[4])

	{

		a[4]--;

		a[3]++;

		a[1]++;

		ans=min(ans,calc());

		a[4]++;

		a[3]--;

		a[1]--;

	}

	if(a[3])

	{

		a[3]--;

		a[1]++;

		a[2]++;

		ans=min(ans,calc());

		a[1]--;

		a[2]--;

		a[3]++;

	}

	if(a[2])

	{

		a[2]--;

		a[1]+=2;

		ans=min(ans,calc());

		a[1]-=2;

		a[2]++;

	}

	return ans;

}

int calc3()

{

	int i;

	memset(a,0,sizeof a);

	int res=0;

	if(s[0]>=2)

		res++;

	else if(s[0]==1)

		a[1]++;

	for(i=1;i<=13;i++)

		a[s[i]]++;

	res+=calc();

	memset(a,0,sizeof a);

	for(i=1;i<=13;i++)

		a[s[i]]++;

	a[1]+=s[0];

	return min(res,calc());

}

void dfs(int now)

{

	if(now>=ans)

		return;

	int v=calc3();

	ans=min(ans,now+v);

	int i,j,k;

	for(i=2;i<=13;i++)

	{

		j=i;

		while(j<=13&&s[j]>=3)

		{

			j++;

			if(j-i>=2)

			{

				for(k=i;k<=j-1;k++)

					s[k]-=3;

				dfs(now+1);

				for(k=i;k<=j-1;k++)

					s[k]+=3;

			}

		}

	}

	for(i=2;i<=13;i++)

	{

		j=i;

		while(j<=13&&s[j]>=2)

		{

			j++;

			if(j-i>=3)

			{

				for(k=i;k<=j-1;k++)

					s[k]-=2;

				dfs(now+1);

				for(k=i;k<=j-1;k++)

					s[k]+=2;

			}

		}

	}

	for(i=2;i<=13;i++)

	{

		j=i;

		while(j<=13&&s[j]>=1)

		{

			j++;

			if(j-i>=5)

			{

				for(k=i;k<=j-1;k++)

					s[k]-=1;

				dfs(now+1);

				for(k=i;k<=j-1;k++)

					s[k]+=1;

			}

		}

	}

	for(i=2;i<=13;i++)

		if(s[i]==4)

		{

			s[i]-=4;

			for(j=i+1;j<=13;j++)

				if(s[j]==4)

				{

					s[j]-=4;

					dfs(now+2);

					s[j]+=4;

				}

			s[i]+=4;

		}

}

void solve()

{

	int x,y;

	memset(s,0,sizeof s);

	int i;

	for(i=1;i<=n;i++)

	{

		scanf("%d%d",&x,&y);

		if(x==1)

			x=13;

		else if(x)

			x--;

		s[x]++;

	}

	ans=0x7fffffff;

	dfs(0);

	printf("%d\n",ans);

}

int main()

{

	int t;

	scanf("%d%d",&t,&n);

	while(t--)

		solve();

	return 0;

}

巴特西

【BZOJ4325】【NOIP2015】斗地主搜索

题目描述

题解

代码

最新文章

热门文章

巴特西

【BZOJ4325】【NOIP2015】斗地主 搜索

题目描述

题解

代码

最新文章

热门文章

【BZOJ4325】【NOIP2015】斗地主搜索