[NOIP2015] 斗地主 大爆搜

考试的时候想了半天,实在是想不到解决的办法,感觉只能暴力。。然后暴力也懒得打了,小数据模拟骗30分hhh

然而正解真的是暴力。。大爆搜。。

然后我的内心拒绝改这道题(TAT)

不过在wcx大佬的帮助下,还是成功的弄过去了。

首先我们明确两个显而易见的问题:答案与花色无关,与出牌顺序无关(废话)

然后我们的切入点是,顺子(连顺等)和带牌(三带一等),因为他们是出牌多的大户。

结论:顺子一定比带牌优(因为可以多出单张)。(不信你可以尝试举出反例)

然后既然这样,我们就先举出全部用带牌的步数,然后一点一点用顺子更新就行了。

有个技巧:按照顺子顺序编号:3,4,5,6···K,A,2。这样的话就可以在循环找顺子的时候方便

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 60
int t,n;
int size[N];
int getnum(int x){//小技巧
	if(x==1)
	  return 12;
	if(x==2)
	  return 13;
	if(x==0)
	  return 14;
	return x-2;
}
int ans;
int doit(){//找到当前剩余牌下全部带牌的最小步骤
	int tmp=0;
	int tp[10]={0};
	pos(i,1,14){
		tp[size[i]]++;
	}
	while(tp[4]&&tp[2]>=2){//四带二
		tp[4]--;tp[2]-=2;tmp++;
	}
	while(tp[4]&&tp[1]>=2){//四带一
		tp[4]--;tp[1]-=2;tmp++;
	}
	while(tp[3]&&tp[2]>=1){//三带二
		tp[3]--;tp[2]-=1;tmp++;
	}
	while(tp[3]&&tp[1]>=1){//三带一
		tp[3]--;tp[1]-=1;tmp++;
	}
	tmp+=tp[1]+tp[2]+tp[3]+tp[4];//单牌
	return tmp;
}
void dfs(int cnt){
	if(cnt>ans)
	  return;
	int x=doit();
	ans=min(ans,cnt+x);
	pos(i,1,11){//三连对
		int j;
		for(j=i;size[j]>=3&&j<=12;j++);
		if(j-i<2)
			continue;
		for(int k=j;k-i>=2;k--){
			pos(l,i,k-1)
			  size[l]-=3;
			dfs(cnt+1);
			pos(l,i,k-1)
			  size[l]+=3;
		}
	}
	pos(i,1,10){//连对
		int j;
		for(j=i;size[j]>=2&&j<=12;j++);
		if(j-i<3)
			continue;
		for(int k=j;k-i>=3;k--){
			pos(l,i,k-1)
			  size[l]-=2;
			dfs(cnt+1);
			pos(l,i,k-1)
			  size[l]+=2;
		}
	}
	pos(i,1,8){//顺子
		int j;
		for(j=i;size[j]>=1&&j<=12;j++);
		if(j-i<5)
			continue;
		for(int k=j;k-i>=5;k--){
			pos(l,i,k-1)
			  size[l]--;
			dfs(cnt+1);
			pos(l,i,k-1){
			  size[l]++;
			}
		}
	}
}
int main(){
	scanf("%d%d",&t,&n);
	while(t--){
		memset(size,0,sizeof(size));
		pos(i,1,n){
			int x,y;
			scanf("%d%d",&x,&y);
			size[getnum(x)]++;
		}
		ans=doit();
		dfs(0);
		printf("%d\n",ans);
	}
	return 0;
}

  

上一篇:docker进入容器方法


下一篇:ST3破解命令