社区讨论

虽然AC了但是有些疑惑求解答

P2915[USACO08NOV] Mixed Up Cows G参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mjk3lcg0
此快照首次捕获于
2025/12/24 22:17
2 个月前
此快照最后确认于
2025/12/27 10:55
2 个月前
查看原帖
用的统计混乱序列过了,但是为什么用统计非混乱序列再拿全排列去减过不了
原本的错误代码:
CPP
#include <bits/stdc++.h>
using namespace std;
unsigned long long n, k, a[20], l[20], r[20], dp[20][(1 << 16) + 10], fac = 1;
int main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) fac *= i; // 计算总组合数 
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n); // 以便于优化
	for (int i = 0, j = 0; i < n; i++) {
		while (a[i] - a[j] > k) j++;
		l[i] = j; 
	}
	for (int i = n - 1, j = n - 1; i >= 0; i--) {
		while (a[j] - a[i] > k) j--;
		r[i] = j;
	}
	for (int i = 0; i < n; i++) dp[i][1 << i] = 1;
	for (int j = 0; j < (1 << n); j++) {
		for (int i = 0; i < n; i++) {
			if (dp[i][j]) continue;
			if (!(j & (1 << i))) continue; // 组合不包含i
			unsigned long long j2 = j ^ (1 << i);
			for (int k = l[i]; k <= r[i]; k++) {
				if (j & (1 << k)) dp[i][j] += dp[k][j2]; 
			}
		}
	}
	unsigned long long ans = fac;
	for (int i = 0; i < n; i++) ans -= dp[i][(1 << n) - 1];
	cout << ans;
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...