社区讨论
0分满江红求条
P1896[SCOI2005] 互不侵犯参与者 3已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @m31n47ip
- 此快照首次捕获于
- 2024/11/03 21:40 去年
- 此快照最后确认于
- 2025/11/04 15:25 4 个月前
Code:
CPP#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define Pii pair<int, int>
#define ULL unsigned long long
namespace gdb7
{
LL dp[10][90][520], ok[520], cnt[520];
int main() {
int n, k2;
cin >> n >> k2;
dp[0][0][0] = 1;
int num = 0;
for (int i = 1; i < (1 << n); ++i) {
int tmp = i;
while (tmp) {
++cnt[i];
tmp &= (tmp - 1);
}
if ((((i << 1) | (i >> 1)) & i) == 0) {
ok[++num] = i;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < num; ++j) {
int s1 = ok[j];
for (int k = 1; k < num; ++k) {
int s2 = ok[k];
if (((s2 | (s2 << 1) | (s2 >> 1)) & s1) == 0) {
for (int l = 0; l <= k2; ++l) {
if (l - cnt[s1] >= 0) {
dp[i][l][s1] += dp[i - 1][l - cnt[s1]][s2];
}
}
}
}
}
}
LL ans = 0;
for (int i = 1; i < num; ++i) {
ans += dp[n][k2][i];
}
cout << ans << endl;
return 0;
}
};
int main()
{
return gdb7::main();
}
全部 WA,样例输出 0。
回复
共 5 条回复,欢迎继续交流。
正在加载回复...