关于搜索优化的疑问
查看原帖
关于搜索优化的疑问
815504
chenwenmo楼主2024/9/23 22:58

想问一下dalao们为什么我的搜索函数里面,对子&单张那块,把注释里的代码改成下面这样就A了

#include<bits/stdc++.h>
using namespace std;
#define min(x,y) ((x>y)?(y):(x))
#define max(x,y) ((x>y)?(x):(y))
#define endl "\n"
#define fst first
#define snd second
#define mk make_pair
typedef __int128 int128;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef unsigned long long ull;

int n, cnt[20], ans = 0x7fffffff;

void search(int tot, int step){
	
	if(step >= ans) return;
	
	if(!tot){
		ans = min(ans, step);
		return;
	}
	
	// 顺子
	for(int i = 3; i >= 1; i--){
		int tmp = 0;
		for(int j = 3; j <= 14; j++){
			if(cnt[j] < i) tmp = 0;
			else tmp++;
			if(i >= 2 && tmp >= 3 || i == 1 && tmp >= 5){
				for(int k = j; k >= j - tmp + 1; k--) cnt[k] -= i;
				search(tot - tmp * i, step + 1);
				for(int k = j; k >= j - tmp + 1; k--) cnt[k] += i;
			}
		}
	}
	
	// 带牌
	for(int i = 2; i <= 14; i++){
		if(cnt[i] >= 4){
			for(int j = 2; j <= 15; j++){
				for(int k = j + 1; k <= 15; k++){
					if(j == i || k == i) continue;
					if(j != 15 && k != 15 && cnt[j] >= 2 && cnt[k] >= 2){
						cnt[i] -= 4, cnt[j] -= 2, cnt[k] -= 2;
						search(tot - 8, step + 1);
						cnt[i] += 4, cnt[j] += 2, cnt[k] += 2;
					}
					if(cnt[j] && cnt[k]){
						cnt[i] -= 4, cnt[j]--, cnt[k]--;
						search(tot - 6, step + 1);
						cnt[i] += 4, cnt[j]++, cnt[k]++;
					}
				}
			}
			cnt[i] -= 4;
			search(tot - 4, step + 1);
			cnt[i] += 4;
		}
		if(cnt[i] >= 3){
			for(int j = 2; j <= 15; j++){
				if(j == i) continue;
				if(cnt[j] >= 2 && j != 15){
					cnt[i] -= 3, cnt[j] -= 2;
					search(tot - 5, step + 1);
					cnt[i] += 3, cnt[j] += 2;
				}
				if(cnt[j]){
					cnt[i] -= 3, cnt[j]--;
					search(tot - 4, step + 1);
					cnt[i] += 3, cnt[j]++;
				}
			}
			cnt[i] -= 3;
			search(tot - 3, step + 1);
			cnt[i] += 3;
		}
	}
	
	// 对子 & 单张 
	/*
	for(int i = 2; i <= 15; i++){
		if(cnt[i] >= 2){
			cnt[i] -= 2;
			search(tot - 2, step + 1);
			cnt[i] += 2;
		}
		if(cnt[i]){
			cnt[i]--;
			search(tot - 1, step + 1);
			cnt[i]++;
		}
	}
	*/
	int tmp = 0;
	for(int i = 2; i <= 15; i++){
		if(cnt[i]) tmp++;
	}
	search(0, step + tmp);
}

void Solve(){
	ans = 0x7fffffff;
	int a, b;
	memset(cnt, 0, sizeof(cnt));
	for(int i = 1; i <= n; i++){
		cin >> a >> b;
		if(a == 0) cnt[15]++;
		else if(a == 1) cnt[14]++;
		else cnt[a]++;
	}
	search(n, 0);
	cout << ans << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T >> n;
	while(T--){
		Solve();
	}
	return 0;
}
2024/9/23 22:58
加载中...