ProjectDP - 27
最基础的状压DP
题目描述
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
注：数据有加强（2018/4/25）
输入输出格式
输入格式
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
输出格式
所得的方案数
输入输出样例
输入样例
输出样例
解题思路
考虑状压DP
我们设 表示第 行的状态的编号为 ，放了 个国王
转移方程显然
MATHJAX-SSR-1251
其中 表示 的二进制1的个数
边界条件：
MATHJAX-SSR-1252
其中 表示当前枚举到的合法的状态
剩下的……就没啥好说的了（
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <iostream>
#include <cstdio>
#include <cstring>
#define IMPIO() std::ios::sync_with_stdio(false);
#define FILE_IN(__file) freopen(__file, 'r', stdin);
#define FILE_OUT(__file) freopen(__file, 'w', stdout);
using std::cin;
using std::cout;
using std::endl;
const int MAXN = 9 + 2;
const int MAXK = MAXN * MAXN;
int n, k;
int stats[(1 << MAXN) - 1 + 10], popc[(1 << MAXN) - 1 + 10], cnt;
long long int dp[MAXN][(1 << MAXN) - 1 + 10][MAXK];
int Popcount(int x) {
int ret = 0;
while (x) {
if (x & 1) ++ret;
x >>= 1;
}
return ret;
}
bool CheckFailed(int stat1, int stat2) {
if ((stat1 & stat2) != 0) return true;
if ((stat1 & (stat2 << 1)) != 0) return true;
if (((stat1 << 1) & stat2) != 0) return true;
return false;
}
int main() {
IMPIO();
cin >> n >> k;
for (int i = 0; i <= (1 << n) - 1; ++i) {
if ((i & (i << 1)) != 0) continue;
stats[++cnt] = i;
dp[1][cnt][Popcount(i)] = 1;
}
for (int i = 2; i <= n; ++i) {
for (int idj = 1; idj <= cnt; ++idj) {
for (int idk = 1; idk <= cnt; ++idk) {
if (CheckFailed(stats[idj], stats[idk])) continue;
for (int l = 0; l <= k; ++l) {
dp[i][idj][Popcount(stats[idj]) + l]
+= dp[i - 1][idk][l];
}
}
}
}
long long int ans = 0;
for (int i = 1; i <= cnt; ++i) {
ans += dp[n][i][k];
}
cout << ans << endl;
return 0;
}
|
