有没有除了改思路以外的优化
查看原帖
有没有除了改思路以外的优化
989571
_ayaka_楼主2024/7/18 17:03

只差两个点,不想大改代码了,求助

#include<bits/stdc++.h>
using namespace std;
#define int long long
int c[20], t, n, x, y, s, d, ans;
#include<cctype>
inline int read() {
	int X = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {
		w |= ch == '-';
		ch = getchar();
	}
	while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
	return w ? -X : X;
}
void dfs(int step, int num) {
	if (step >= ans) return ;
	if (num == 0) {
		ans = min(ans, step);
		return ;
	}
//	for(int i=2;i<=15;i++) cout<<c[i]<<" ";
//	cout<<"\n"<<step<<" "<<num<<"\n\n";
	int s1 = 0, s2 = 0, s3 = 0;
	for (int i = 3; i <= 14; i++) {
		s1++;
		s2++;
		s3++;
		if (!c[i]) s1 = 0;
		if (c[i] < 2) s2 = 0;
		if (step + 1 >= ans) return ;
		if (c[i] < 3) s3 = 0;
//		cout<<s1<<" "<<s2<<" "<<s3<<"  114514\n";
		if (s3 >= 2) {
			for (int j = i; j >= i - s3 + 1; j--) c[j] -= 3;
			dfs(step + 1, num - s3 * 3);
			for (int j = i; j >= i - s3 + 1; j--) c[j] += 3;
		}
		if (step + 1 >= ans) return ;
		if (s2 >= 3) {
			for (int j = i; j >= i - s2 + 1; j--) c[j] -= 2;
			dfs(step + 1, num - s2 * 2);
			for (int j = i; j >= i - s2 + 1; j--) c[j] += 2;
		}
		if (step + 1 >= ans) return ;
		if (s1 >= 5) {
			for (int j = i; j >= i - s1 + 1; j--) c[j]--;
			dfs(step + 1, num - s1);
			for (int j = i; j >= i - s1 + 1; j--) c[j]++;
		}
		if (step + 1 >= ans) return ;
	}
//	cout<<"1\n";
	for (int i = 2; i <= 14; i++) {
		if (c[i] == 4) {
			c[i] -= 4;
			for (int j = 2; j <= 14; j++) { //四带二对
				if (c[j] >= 2) {
					c[j] -= 2;
					for (int k = 2; k <= 14; k++) {
						if (c[k] >= 2) {
							c[k] -= 2;
							dfs(step + 1, num - 8);
							c[k] += 2;
						}
					}
					c[j] += 2;
				}
			}
			if (step + 1 >= ans) return ;
			for (int j = 2; j <= 15; j++) {//四带二
				if (c[j]) {
					c[j] --;
					for (int k = 2; k <= 15; k++) {
						if (c[k]) {
							c[k] --;
							dfs(step + 1, num - 6);
							c[k] ++;
						}
					}
					c[j] ++;
				}
				if (step + 1 >= ans) return ;
			}
			c[i] += 4;
		}
	}
	if (step + 1 >= ans) return ;
//	cout<<"2\n";
	for (int i = 2; i <= 14; i++) {
		if (c[i] >= 3) {
			c[i] -= 3;
			for (int j = 2; j <= 14; j++) { //三带一对
				if (c[j] >= 2) {
					c[j] -= 2;
					dfs(step + 1, num - 5);
					c[j] += 2;
				}
			}
			if (step + 1 >= ans) return ;
			for (int j = 2; j <= 15; j++) { //三带一
				if (c[j]) {
					c[j] --;
					dfs(step + 1, num - 4);
					c[j] ++;
				}
			}
			if (step + 1 >= ans) return ;
			c[i] += 3;
		}
	}
	if (step + 1 >= ans) return ;
//	cout<<"3\n";
	for (int i = 2; i <= 15; i++) {
		if (c[i]) step++;
	}

	dfs(step, 0);
	return ;
}
signed main() {
	cin >> t >> n;
	while (t--) {
		ans = 0x3f3f3f3f3f;
		for (int i = 1; i <= n; i++) {
			x = read();
			y = read();
			if (x == 1) c[14]++;
			else if (x == 0) c[15]++;
			else c[x]++;
		}
//		for(int i=2;i<=15;i++) cout<<c[i]<<" ";
//		cout<<"\n";
		dfs(0, n);
		cout << ans << "\n";
		for(int i=2;i<=15;i++) c[i]=0;
	}
	return 0;
}
2024/7/18 17:03
加载中...