题目大意

有以下几种出牌形式：

问你最少几次可以出完手牌。

注意：

双王不可以当对子带，但可以当单牌带。
四带两对可以带四张相同的牌，四带二可以带对子。

思路

暴力出奇迹，考虑直接 DFS 暴力，枚举所有的方案，直接暴力出最少的次数。
暴力顺序：单顺子

\to

双顺子

\to

三顺子

\to

三带一

\to

三带二

\to

四带二

\to

四带两对

\to

散牌。
（这只是我的顺序，别的应该也行）。
你们可能会说，这会 TLE。
考虑剪枝优化。
只要加上

CPP

if(x>=ans) //x是当前次数，ans是最后的答案
    return;

就能减掉大部分的时间。因为当前次数已经超过了最优次数，就没必要往下搜了。
你们又要说了，还是会 TLE，没有用。
怎么办呢，我们就能使用信仰一剪。
考虑通过计数器来统计 DFS 的次数，达到一定值后退出来卡时间（我选的值是

1 \times 10^6

）。

CPP

int dfn;
void dfs(int x)
{
    if(++dfn>1000000) 
        return;
...........

这样就能愉快的 AC 了。
就下来就是...

AC 代码

~~配合注释食用更佳。~~

CPP

#include<bits/stdc++.h>
using namespace std;
#define Tie ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) //快读
int T,n,ans,sum[25]; //T组数，n牌数，ans答案，sum记录牌数
int dfn; //记录dfs次数
void dfs(int x) //x记录次数
{
    if(++dfn>1000000) //剪枝优化1
        return;
	if(x>=ans) //剪枝优化2
        return;
	int k=0;
    //单顺子
	for(int i=3;i<=14;i++)
	{
		if(sum[i]==0) 
            k=0; //顺子断了,k清零
		else
		{
			k++; //顺子长度加一
			if(k>=5) //如果顺子长度大于等于5
			{
				for(int j=i-k+1;j<=i;j++) 
                    sum[j]--; //顺子中的牌数减一
				dfs(x+1); //搜下一层
				for(int j=i-k+1;j<=i;j++)  
                    sum[j]++;   //回溯
			}
		}
	}
	k=0; //清零
    //双顺子
	for(int i=3;i<=14;i++)
	{
		if(sum[i]<2) 
            k=0; //双顺子断了,k清零
		else 
		{
			k++; //双顺子长度加一
			if(k>=3) //如果双顺子长度大于等于3
            {
                for(int j=i-k+1;j<=i;j++) 
                    sum[j]-=2; //双顺子中的牌数减二
                dfs(x+1); //搜下一层
                for(int j=i-k+1;j<=i;j++) 
                    sum[j]+=2; //回溯
            }
		}
	}
	k=0;
    //三顺子
	for(int i=3;i<=14;i++)
	{
		if(sum[i]<=2) 
            k=0; //三顺子断了,k清零
		else 
		{
			k++;    //三顺子长度加一
			if(k>=2) //如果三顺子长度大于等于2
			{
				for(int j=i-k+1;j<=i;j++)
                    sum[j]-=3; //三顺子中的牌数减三
				dfs(x+1);
				for(int j=i-k+1;j<=i;j++)
                    sum[j]+=3;  //回溯
			}
		}
	}
    //以下原理同上
	for(int i=2;i<=14;i++)
	{
		if(sum[i]==3) //三带
        {
			sum[i]-=3;
			for(int j=2;j<=15;j++) //三带一
			{
				if(sum[j]<1||j==i) 
                    continue;
				sum[j]--;
				dfs(x+1);
				sum[j]++;
			}
			for(int j=2;j<=14;j++) //三带二
            {
                if(sum[j]<2||j==i) 
                    continue;
                sum[j]-=2;
                dfs(x+1);
                sum[j]+=2;
            }
			sum[i]+=3;
		} 
		if(sum[i]==4)//四带
		{
			sum[i]-=4;
			for(int j=2;j<=15;j++) //四带二
            {
				if(sum[j]<1||j==i) 
                    continue;
				sum[j]--;
				for (int k=2;k<=15;k++)
				{
					if(sum[k]<1) 
                        continue;
					sum[k]--;
					dfs(x+1);
					sum[k]++;
				}
				sum[j]++;
			}
			for(int j=2;j<=14;j++) //四带两对
			{
				if(sum[j]<2||j==i) 
                    continue;
				sum[j]-=2;
				for(int k=2;k<=14;k++) 
				{
					if(sum[k]<2) 
                        continue;
					sum[k]-=2;
					dfs(x+1);
					sum[k]+=2;
				}
				sum[j]+=2;
			}
			sum[i]+=4;
		}
	}
	for(int i=2;i<=15;i++) 
        if(sum[i]) 
            x++; //没出完的，无论是单张，对子，三张，四张都可以一次出完
	ans=min(ans,x); //更新答案
}
int main() 
{
    Tie;
	cin>>T>>n; 
	while(T--) 
	{
        dfn=0; //初始化1
		ans=INT_MAX;  //初始化2
		memset(sum,0,sizeof sum); //初始化3
		for(int i=1;i<=n;i++)
		{
            int x,y;
            cin>>x>>y;
			if(x==0) x=15; //0是大小王，算到15里
			if(x==1) x=14; //1是A，算到14里，因为A最大
		    sum[x]++; //记录牌数
		}
		dfs(0); //dfs
        cout<<ans<<'\n'; //输出答案
	}
}

双倍经验: P2668 [NOIP2015 提高组] 斗地主

题解：P2540 [NOIP2015 提高组] 斗地主加强版

文章操作

题目大意

思路

AC 代码

相关推荐

评论

题解：P2540 [NOIP2015 提高组] 斗地主加强版