社区讨论
虽然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 条回复,欢迎继续交流。
正在加载回复...