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

时间：2023-03-08 22:20:16

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;

}

相关文章