题目描述
在 $n \times n$ 的棋盘上放 $k$ 个国王,国王可攻击相邻的 $8$ 个格子,求使它们无法互相攻击的方案总数。
输入格式
共一行,包含两个整数 $n$ 和 $k$。
输出格式
共一行,表示方案总数,若不能够放置则输出$0$。
数据范围
$1 \le n \le 10$,
$0 \le k \le n^2$
输入样例:
3 2
输出样例:
16
算法
状态压缩DP
f[i,b,k]表示第i行的状态为b放了k个国王的方案数目
初始化一开始方案为1
然后dp每一行,枚举上下两行的状态ab,
如果国王重合或者国王相邻都不需要
时间复杂度
101024100 差不多1e7 可以过的
空间复杂度
write here…
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 11, M = 1 << N, K = 100;
long long f[N][M][K]; // f[i,b,k]表示第i行的状态为b放了k个国王的方案数目
int n, k;
int get_count(int x)
{
int res = 0;
while(x)
{
res++;
x -= x & -x;
}
return res;
}
int main()
{
cin >> n >> k;
f[0][0][0] = 1;
for(int i = 1; i <= n; i++)
{
for(int a = 0; a < 1 << n; a++)
{
for(int b = 0; b < 1 << n;b ++)
{
int x = a | b;
if(a & b || x & (x >> 1)) continue;
int t = get_count(b);
for(int cnt = t; cnt <= k; cnt++)
f[i][b][cnt] += f[i-1][a][cnt - t];
}
}
}
long long res = 0;
for(int i = 0; i < 1 << n; i++)
res += f[n][i][k];
cout << res;
return 0;
}