[NOIP2015提高组]斗地主（贪心+搜索）

本文主要是介绍[NOIP2015提高组]斗地主（贪心+搜索），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

15 年的 NOIP 提高组试题，被搬到今天校模拟赛，只糊了 20 分，结果人均 50 分贪心……

这张图片可以作为题目描述：

并不是跟别人斗地主，而是要求尽快出完牌，输出步数。 \(n \le 20\)，多组数据。

对于 \(n \le 5\) 的那些测试点，当然可以手工模拟。更进一步，根据打牌的经验（显然我就没有），不难产生一些贪心思路，例如先出顺子、尽可能四带二、三带二、三带一等。

稍加考虑，一般的贪心都是错误的——只能采取搜索了。然而搜索的时间复杂度很高，O(TLE)，所以需要剪枝。

• 贪心地搜索。每一次出牌是一个阶段，分为顺子、双顺子、三顺子、四带二、三带二、三带一 6 种出牌方式，向下递归，回溯；

• 最优化剪枝。如果当前出牌次数大于等于当前答案，直接返回；

• 不在“一个三、一个五”这样的零散牌上费时间，在函数体最后扫一遍剩下的牌，步数++即可。

代码实现上有很多细节，例如大小王的判断（出对子时永远 13 种牌，单出才有 14 种）或 A 的判断（它可以作为对子或顺子的一部分）。下附 AC 代码。

#include<bits/stdc++.h>
using namespace std;
inline int rd(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-') f^=1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f?x:-x;
}
int T,n,ans,a[30];
void dfs(int d){
	if(d>=ans) return;
	//1. 顺子(5)
	for(int l=3;l<=10;++l){
		if(!a[l]) continue;
		int r=l+1;
		while(r<=13&&a[r]) ++r;--r;
		if(r==13&&a[1]) ++r;
		//最长[l,r]
		if(r-l+1<5) continue;
		for(int i=l+4;i<=r;++i){
			for(int j=l;j<=i;++j)
				if(j<=13) --a[j];
				else --a[1];
			dfs(d+1);
			for(int j=l;j<=i;++j) 
				if(j<=13) ++a[j];
				else ++a[1];
		}
	} 
	//2. 双顺子(3)
	for(int l=3;l<=12;++l){
		if(a[l]<2) continue;
		int r=l+1;
		while(r<=13&&a[r]>=2) ++r;--r;
		if(r==13&&a[1]>=2) ++r;
		if(r-l+1<3) continue;
		for(int i=l+2;i<=r;++i){
			for(int j=l;j<=i;++j)
				if(j<=13) a[j]-=2;
				else a[1]-=2;
			dfs(d+1);
			for(int j=l;j<=i;++j)
				if(j<=13) a[j]+=2;
				else a[1]+=2;
		}
	} 
	//3. 三顺子(2)
	for(int l=3;l<=13;++l){
		if(a[l]<3) continue;
		int r=l+1;
		while(r<=13&&a[r]>=3) ++r;--r;
		if(r==13&&a[1]>=3) ++r;
		if(r-l+1<2) continue;
		for(int i=l+1;i<=r;++i){
			for(int j=l;j<=i;++j)
				if(j<=13) a[j]-=3;
				else a[1]-=3;
			dfs(d+1);
			for(int j=l;j<=i;++j)
				if(j<=13) a[j]+=3;
				else a[1]+=3;
		}
	}
	//4. 四带二 
	for(int i=1;i<=13;++i){
		if(a[i]<4) continue;
		a[i]=0;
		//4.1 带两张零牌 / 一个对子  
		for(int j=1;j<=14;++j){
			if(!a[j]) continue;
			--a[j];
			for(int k=1;k<=14;++k){
				if(!a[k]) continue;
				--a[k],dfs(d+1),++a[k];
			}
			++a[j];
		}
		//4.2 带两个对子 
		for(int j=1;j<=13;++j){
			if(a[j]<2) continue;
			a[j]-=2;
			for(int k=1;k<=13;++k){
				if(a[k]<2) continue;
				a[k]-=2,dfs(d+1),a[k]+=2;
			}
			a[j]+=2;
		} 
		a[i]=4;
	} 
	//5. 三带二 / 三带一 
	for(int i=1;i<=13;++i){
		if(a[i]<3) continue;
		a[i]-=3;
		for(int j=1;j<=13;++j){
			if(a[j]<2||i==j) continue;
			a[j]-=2,dfs(d+1),a[j]+=2;
		}
		for(int j=1;j<=14;++j){
			if(!a[j]||i==j) continue;
			--a[j],dfs(d+1),++a[j];
		}
		a[i]+=3;
	} 
	//6. 零牌 
	for(int i=1;i<=14;++i)
		if(a[i]) ++d;
	ans=min(ans,d);
}
int main(){
	T=rd(),n=rd();
	while(T--){
		ans=0x7fffffff;
		memset(a,0,sizeof(a));
		for(int i=1,x,y;i<=n;++i){
			x=rd(),y=rd();
			x?++a[x]:++a[14];
		}
		dfs(0);
		printf("%d\n",ans);
	}
	return 0;
}

THE END

这篇关于[NOIP2015提高组]斗地主（贪心+搜索）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！