P1896 [SCOI2005] 互不侵犯

2023年9月26日#oi6

AI 生成的摘要

在一个 $N \times N$ 的棋盘上放置 $K$ 个国王，使其互不攻击，问题是计算有多少种摆放方案。国王可以攻击其周围的八个格子。对于所有数据，$1 \le N \le 9$，$0 \le K \le N \times N$。解法是使用动态规划，定义状态 fi[k] 表示在第 i 行选择 j 个国王，状态为 k 的方案数，通过枚举行、国王数量和前一行状态进行转移。代码实现中需要注意数据类型和状态转移的条件。

题目#

[SCOI2005] 互不侵犯#

题目描述#

在 $N \times N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。
对于全部数据，$1 \le N \le 9$，$0 \le K \le N\times N$。

题解#

设f[i][j][k]表示推到了第 i 行，到目前为止选了 j 个国王，第 i 行的状态为 k 的方案数

然后枚举i,j,k以及前一行的状态转移即可

问题#

1. 不开long long见祖宗

2. 第二位要开N * N！

代码#

#include<bits/stdc++.h>
#define int long long
using namespace std;

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}
const int N = 10;
int f[N][N * N][1 << 9];
int sum[1 << 9];
int n, k;

int getsum(int x)
{
	int ans = 0;
	while(x)
	{
		x &= (x - 1);
		ans++;
	}
	return ans;
}

signed main()
{
	for(int i = 0;i < (1 << 9);i++)
	{
		sum[i] = getsum(i);
	}
	n = read(), k = read();
	for(int s = 0;s < (1 << n);s++)
	{
		f[1][sum[s]][s] = 1;
	}

	for(int i = 2;i <= n;i++)
	{
		for(int j = 0;j <= k;j++)
		{
			for(int s = 0;s < (1 << n);s++)
			{
				if((s >> 1) & s || (s << 1) & s || sum[s] > j) continue;
				for(int fl = 0;fl < (1 << n);fl++)
				{
					if((fl >> 1) & fl || (fl << 1) & fl || (fl << 1) & s || fl & s || (fl >> 1) & s || sum[fl] + sum[s] > j) continue;
					f[i][j][s] += f[i - 1][j - sum[s]][fl];
				}
			}
		}

	}

	long long ans = 0;
	for(int s = 0; s < (1 << n);s++)
	{
		if((s >> 1) & s) continue;
			ans += f[n][k][s];
	}
	cout << ans;
	return 0;
}