TLE45分求调
查看原帖
TLE45分求调
714692
zzy_vector楼主2024/10/1 22:59

调了快 33 个小时了,救救孩子吧!!!

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
int t,n,a,b;
int ans;
int card[25];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
		ch=getchar();
	}
    return x*f;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return;
}
void dfs(int x){//x表示当前的出牌次数 
	if(x>=ans){
		return;
	}
	//先出单顺子(不包括2点和双王)
	int k=0;//k表示当前扔出的牌数 
	for (int i=3;i<=14;i++){
		if(card[i]==0){
			k=0;//断了 
		}
		else{
			k++;//多了一个牌
			if(k>=5){//单顺子至少出5张 
				for (int j=i;j>=i-k+1;j--){//因为是连续的 
					card[j]--;//出牌 
				}
				dfs(x+1);//继续搜索
				for (int j=i;j>=i-k+1;j--){
					card[j]++;//回溯 
				} 
			} 
		}
	}
	//2.出双顺子(不包括2点和双王)
	k=0;//这里记录几组 
	for (int i=3;i<=14;i++){
		if(card[i]<=1){
			k=0;//断了 
		}
		else{
			k++;
			if(k>=3){//至少有3对 
				for (int j=i;j>=i-k+1;j--){
					card[j]-=2;
				}//出牌 
				dfs(x+1);
				for (int j=i;j>=i-k+1;j--){
					card[j]+=2;
				}
			}
		}
	}
	//3.出三顺子(不包括2点和双王)
	k=0;//这里记录三张牌的出现的次数 
	for (int i=3;i<=14;i++){
		if(card[i]<=2){
			k=0;
		}
		else{
			k++;
			if(k>=2){
				for (int j=i;j>=i-k+1;j--){
					card[j]-=3;
				}
				dfs(x+1);
				for (int j=i;j>=i-j+1;j--){
					card[j]+=3;
				}
			}
		}
	}
	//4出带牌(单张可以带大小王)
	for (int i=2;i<=14;i++){
		if(card[i]<=3){//三带一 
			if(card[i]<=2){
				continue;
			}
			card[i]-=3;
			for (int j=2;j<=15;j++){//出单牌 
				if(card[j]<=0||i==j){
					continue;
				}
				card[j]--;
				dfs(x+1);
				card[j]++;
			} 
			for (int j=2;j<=14;j++){//出对牌 
				if(card[j]<=1||j==i){
					continue;
				}
				card[j]-=2;
				dfs(x+1);
				card[j]+=2;
			}
			card[i]+=3;
		}
		else{//大于三张牌的可以选择4张牌或者3张牌 
			card[i]-=3;//3带的
			for (int j=2;j<=15;j++){//出单牌 
				if(card[j]<=0||j==i){
					continue;
				}
				card[j]--;
				dfs(x+1);
				card[j]++;
			} 
			for (int j=2;j<=14;j++){//出对牌 
				if(card[j]<=1||i==j){
					continue;
				}
				card[j]-=2;
				dfs(x+1);
				card[j]+=2;
			}
			card[i]+=3;
			card[i]-=4;//4张牌带的
			for (int j=2;j<=15;j++){//带两个单张 
				if(card[j]<=0||j==i){
					continue;
				}
				card[j]--;
				for (int k=2;k<=15;k++){
					if(card[k]<=0||k==j){
						continue;
					}
					card[k]--;
					dfs(x+1);
					card[k]++;
				}
				card[j]++;
			}
			for (int j=2;j<=14;j++){//带两个对 
				if(card[j]<=1||i==j){
					continue;
				}
				card[j]-=2;
				for (int k=2;k<=14;k++){
					if(k==i||card[k]<=1){
						continue;
					}//一对牌可以算两张牌 
					card[k]-=2;
					dfs(x+1);
					card[k]+=2;
				}
				card[j]+=2;
			}
			card[i]+=4; 
		}
	}
	//cout<<1<<"\n";
	for (int i=2;i<=15;i++){//把剩下的牌出完 
		if(card[i]){
			x++;
		}//由于大小王和对子可以同时出,所以算一次 
	}
	ans=min(ans,x);
}
int main(){
	t=read();
	n=read();
	while(t--){
		ans=0x7fffffff;
		memset(card,0,sizeof(card));
		for (int i=1;i<=n;i++){
			a=read();
			b=read();
			if(a==1){
				card[14]++;
			}//处理A牌 
			else if(a==0){
				card[15]++;
			}//处理大小王,当做双牌处理即可 
			else card[a]++;
		}
		dfs(0);
		write(ans);
		printf("\n");
	}
	return 0;
}

测评记录:here

如果是剪枝的问题,请指出,或是代码逻辑错误,谢谢了。

2024/10/1 22:59
加载中...