【BZOJ 1087】【SCOI 2005】互不侵犯King

http://www.lydsy.com/JudgeOnline/problem.php?id=1087

很简单的状压,需要预处理,我两个状态可不可以挨着的预处理出错WA了好几次。

这个位运算预处理好神奇啊

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 10;
int in() {
int k = 0; char c = getchar();
for (; c < '0' || c > '9'; c = getchar());
for (; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - 48;
return k;
} bool can[1 << 9], c[1 << 9][1 << 9];
ll f[N][N * N][1 << 9];
int tot, n, K, num[1 << 9];
bool flag; int main() {
n = in(); K = in(); tot = (1 << n) - 1;
for (int i = 0; i <= tot; ++i)
if (can[i] = !(i & (i >> 1)))
for (int j = 0; j < n; ++j)
if ((1 << j) & i)
++num[i];
for (int i = 0; i < tot; ++i)
if (can[i])
for (int j = i + 1; j <= tot; ++j)
if (can[j])
c[i][j] = c[j][i] = !(i & j) && !(i & (j >> 1)) && !(j & (i >> 1));
c[0][0] = true; f[0][0][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = min(K, i * n); j >= 0; --j)
for (int k = 0; k <= tot; ++k)
if (can[k])
for (int l = 0; l <= tot; ++l)
if (can[l] && c[k][l] && num[l] <= j)
f[i][j][l] += f[i - 1][j - num[l]][k]; ll ans = 0;
for(int i = 0; i <= tot; ++i)
ans += f[n][K][i];
printf("%lld\n", ans);
return 0;
}
上一篇:Problem D: 求(x-y+z)*2


下一篇:趣图:当我捕获Bug的时候