求助
查看原帖
求助
729386
_Fancy_楼主2024/1/25 18:36

查了半天,才18分,实在找不出错了

#include <bits/stdc++.h>
using namespace std;
int T, n, ans;
int a[16], c[5];
int dp[57][30][20][15];

void dfs(int x) {
	if(x >= ans) return;
	memset(c, 0, sizeof c);
	for(int i = 1; i <= 13; i++) {
		c[a[i]]++;
	}
	ans = min(ans, x + dp[c[1] + a[14]][c[2]][c[3]][c[4]]);
	if(a[14] == 2) ans = min(ans, x + dp[c[1]][c[2]][c[3]][c[4]] + 1);
	for(int dd = 1; dd <= 3; dd++) {
		for(int i = 2; i <= 13; i++) {
			int cnt = 0;
			for(int j = i; j <= 13; j++) {
				if(a[i] >= dd) cnt++;
				else break;
				if(dd * cnt >= 5) {
					for(int k = i; k < i + cnt; k++) {
						a[k] -= dd;
					}
					dfs(x + 1);
					for(int k = i; k < i + cnt; k++) {
						a[k] += dd;
					}
				}
			}
		}
	}
	for(int i = 1; i <= 14; i++) {
		if(a[i] > 0) x++;
	}
	ans = min(ans, x);
}
void init() {
	memset(dp, 0x3f, sizeof dp);
	dp[0][0][0][0] = 0;
	for (int l = 0; l <= 13; l++) {
		for (int k = 0; k <= 18; k++) {
			for (int j = 0; j <= 27; j++) {
				for (int i = 0; i <= 54; i++) {
					int x = 100;
					if(i > 0) {
						x = min(x, dp[i - 1][j][k][l] + 1);
					}
					if(j > 0) {
						x = min(x, dp[i][j - 1][k][l] + 1);
					}
					if(k > 0) {
						x = min(x, dp[i][j][k - 1][l] + 1);
					}
					if(l > 0) {
						x = min(x, dp[i][j][k][l - 1] + 1);
					}
					if(i > 0 && k > 0) {
						x = min(x, dp[i - 1][j][k - 1][l] + 1);
					}
					if(j > 0 && k > 0) {
						x = min(x, dp[i][j - 1][k - 1][l] + 1);
					}
					if(i > 1 && l > 0) {
						x = min(x, dp[i - 2][j][k][l - 1] + 1);
					}
					if(j > 0 && l > 0) {
						x = min(x, dp[i][j - 1][k][l - 1] + 1);
					}
					if(j > 1 && l > 0) {
						x = min(x, dp[i][j - 2][k][l - 1] + 1);
					}
					if(l > 1) {
						x = min(x, dp[i][j][k][l - 2] + 1);
					}
					if(l > 0) {
						x = min(x, dp[i + 1][j][k + 1][l - 1]);
					}
					if(k > 0) {
						x = min(x, dp[i + 1][j + 1][k - 1][l]);
					}
					dp[i][j][k][l] = min(dp[i][j][k][l], x);
				}
			}
		}
	}
}

int main() {
	scanf("%d%d", &T, &n);
	init();
	while (T--) {
		memset(a, 0, sizeof(a));
		ans = n;
		for (int i = 1, x, y; i <= n; i++) {
			scanf("%d%d", &x, &y);
			if(x == 0) {
				a[14]++;
			}
			if(x >= 3) {
				a[x - 2]++;
			}
			if(x == 1) {
				a[12]++;
			}
			if(x == 2) {
				a[13]++;
			}
		}
		dfs(0);
		printf("%d\n",ans);
	}
	return 0;
}
2024/1/25 18:36
加载中...