题目大意

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。（ 1 <=N <=9, 0 <= K <= N * N）

题解

这跟“炮兵阵地”很是相似。定义一行的状态\(S\)为是否安放国王的01集合。先预处理出一行中两两国王无法攻击的所有状态（以后简称合理状态），以及这些状态中1的个数\(g(S)\)。定义\(f(r,S,k)\)为当第\(r\)行的状态为\(S\)时，1至\(r\)行中存在\(k\)个国王的安排有多少种。则递归式为：

\[f(r,S,k)=\sum_{S'\And(S|(S<<1)|(S>>1))=0}f(r-1,S',k-g(S))
\]

实际上，S用可行状态的编号表示即可。

注意

f数组中用来存放S的大小应当是1<<MAX_N，而不是MAX_N，因为合理状态的数量可能比N多，最大编号也就比N多了。
注意递归式中与\(S'\)与操作的还有\(S\)。
最后统计结果时，枚举S的终止条件为达到最大合理状态的编号，而不是N。注意下定义。

关于暴力

一个一个枚举国王可能在的位置。因为重合子问题\(f(r,S,k)\)被计算了多次，故不是正解。但是要做到正确，注意：

用来恢复现场的数据应当保存在系统栈内，而不是放在堆中供多次递归函数共用。这就错了。
仔细检查，防止手误。

AC代码：

#include <cstdio>

#include <cstring>

#include <bitset>

#include <iostream>

using namespace std;

#define ll long long

const int MAX_N = 10, MAX_K = 100;

ll F[MAX_N][1<<MAX_N][MAX_K];

int States[1<<MAX_N], State1Cnt[1<<MAX_N];

int N, StCnt, K;

void GetProperState(int n)

{

	StCnt = 0;

	for (int i = 0; i <= ~(~1 << n - 1); i++)

	{

		if (!(i << 1 & i))

		{

			States[StCnt] = i;

			int temp = i;

			while (temp)

			{

				if (temp & 1)

					State1Cnt[StCnt]++;

				temp >>= 1;

			}

			StCnt++;

		}

	}

}

void PrintBinary(ll x)

{

	cout << bitset<5>(x);

}

ll DP()

{

	ll ans = 0;

	for (int i = 0; i <= StCnt; i++)

		F[0][i][State1Cnt[i]] = 1;

	for (int level = 1; level < N; level++)

		for (int i = 0; i < StCnt; i++)

			for (int j = 0; j < StCnt; j++)

				if (!(States[i]&States[j])&&!((States[i] << 1) & States[j]) && !((States[i] >> 1) & States[j]))

					for (int k = State1Cnt[i]; k <= K; k++)

						F[level][i][k] += F[level - 1][j][k - State1Cnt[i]];

	for (int i = 0; i < StCnt; i++)

		ans += F[N - 1][i][K];

	return ans;

}

int main()

{

	scanf("%d%d", &N, &K);

	GetProperState(N);

	printf("%lld\n", DP());

	return 0;

}

巴特西

luogu1896 [SCOI2005]互不侵犯状压DP

题目大意

题解

注意

关于暴力

最新文章

热门文章

巴特西

luogu1896 [SCOI2005]互不侵犯 状压DP

题目大意

题解

注意

关于暴力

最新文章

热门文章

luogu1896 [SCOI2005]互不侵犯状压DP