|
|
##[$AcWing$ $1064$. 小国王](https://www.acwing.com/problem/content/1066/)
|
|
|
### 一、题目描述
|
|
|
在 $n×n$ 的棋盘上放 $k$ 个国王，国王可攻击相邻的 $8$ 个格子，求使它们无法互相攻击的方案总数。
|
|
|
|
|
|
**输入格式**
|
|
|
共一行，包含两个整数 $n$ 和 $k$。
|
|
|
|
|
|
**输出格式**
|
|
|
共一行，表示方案总数，若不能够放置则输出$0$。
|
|
|
|
|
|
**数据范围**
|
|
|
$1≤n≤10,0≤k≤n^2$
|
|
|
|
|
|
**输入样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
3 2
|
|
|
```
|
|
|
|
|
|
**输出样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
16
|
|
|
```
|
|
|
### 二、题目理解
|
|
|
|
|
|
国王可以向附近的 **八个方向** 进行攻击，所以穷举一下十六种可能，与测试用例对上了。
|
|
|
|
|
|
### 三、题目解析
|
|
|
|
|
|
一个国王能攻击它 **相邻** 的$8$个格子:
|
|
|
```cpp {.line-numbers}
|
|
|
↖ ↑ ↗
|
|
|
← ㊣ →
|
|
|
↙ ↓ ↘
|
|
|
```
|
|
|
|
|
|
|
|
|
根据$DP$的一般思考方式，假想已经完成前$i-1$行的摆放，现在处在第$i$行，可行的搬放方法是：
|
|
|
|
|
|
* ① 同行不能 **连续** 放国王
|
|
|
|
|
|
与上一行对比(**每一行都考虑与前一行的关系，就解决了所有关系**)，
|
|
|
* ② 如果上一行某列放了国王，此列就不能放国王
|
|
|
* ③ 如果上一行某列放了国王，此列的$45$度方向也不能放国王
|
|
|
|
|
|
#### 1、状态表示
|
|
|
因为上一行的摆放方法，直接影响了本行的摆放，所以记录上一行的摆放情况是必要的。怎么记录呢？考虑到数字$n$较小，大约在$10$左右，这就明显是在提示我们可以采用 **状态压缩** 来描述状态。数位上是$1$表示要摆，数位上是$0$表示不摆。
|
|
|
|
|
|
#### 2、同行不能连续放国王
|
|
|
常规思路是枚举每一个二进制数位，判断本位与下一位是不是都是数字$1$。
|
|
|
本题$n=10$最大，就是每判断一个数字是不是合法状态，需要判断$10$次。
|
|
|
|
|
|
**位运算会使得运算更快捷**：
|
|
|
```cpp {.line-numbers}
|
|
|
bool check(int x) {
|
|
|
return !(x & x >> 1);
|
|
|
}
|
|
|
```
|
|
|
只需一步，$O(1)$，性能提高十倍！$x$与$x>>1$进行相与，如果$x$有连续的数字，那么必
|
|
|
|
|
|
<!-- 让表格居中显示的风格 -->
|
|
|
<style>
|
|
|
.center
|
|
|
{
|
|
|
width: auto;
|
|
|
display: table;
|
|
|
margin-left: auto;
|
|
|
margin-right: auto;
|
|
|
}
|
|
|
</style>
|
|
|
<div class="center">
|
|
|
|
|
|
| $x$ | $1100$ |
|
|
|
| ----------- | ------ |
|
|
|
| $x>>1$ | $0110$ |
|
|
|
| $x\&(x>>1)$ | $0100$ |
|
|
|
</div>
|
|
|
|
|
|
错位相与，结果大于$0$，就表示存在连续的$1$
|
|
|
|
|
|
> <font color='red' size=4><b> 结论：
|
|
|
> 错位相与，结果大于$0$，表示存在连续的$1$
|
|
|
> </b></font>
|
|
|
|
|
|
#### 3、与上一行对比，如果上一行某列放了国王，此列就不能放国王
|
|
|
```cpp {.line-numbers}
|
|
|
(a & b) == 0
|
|
|
```
|
|
|
上一行的状态$a$与本行的状态$b$,如果按位相与，结果为$0$，就是没有同列是$1$的情况。
|
|
|
|
|
|
> <font color='red' size=4><b> 结论：
|
|
|
> 上下相与，结果等于$0$，不存在同列数字$1$
|
|
|
</b></font>
|
|
|
|
|
|
#### 4、与上一行对比，如果上一行某列放了国王，此列的45度方向也不能放国王
|
|
|
```cpp {.line-numbers}
|
|
|
check(a | b)
|
|
|
```
|
|
|
这个就更妙了，先用$a|b$,只要$a$或$b$的某一列有一个是$1$，那么本列结果就是$1$，起到了一个叠加的作用，这个结果，是在保证了上面同行没有连续数位是$1$的情况下进行讨论，此时，结果出现了连续$1$，只能是$a$与$b$存在 **错列** 连续$1$的情况，也就是$45$度相关。
|
|
|
|
|
|
> <font color='red' size=4><b> 结论：
|
|
|
> 在保证上下两行没有连续数位是$1$的情况下讨论, 上下相与，再做错位相与，可检查上下两行是否存在$45^\circ$度两个数字$1$</b></font>
|
|
|
|
|
|
### 四、动态规划
|
|
|
#### 状态表示
|
|
|
|
|
|
**集合**
|
|
|
$f[i][j][k]$ 表示前$i$行已经摆完，放入了$j$个国王，并且 <font color='red' size=4><b>第$i$行状态是$k$</b></font> 的所有方案。
|
|
|
|
|
|
**属性**
|
|
|
方案个数
|
|
|
|
|
|
#### 状态计算
|
|
|
本行的预放入状态，需要与上一行 **兼容**，并且本行预放入的状态中包含的国王个数，需要小于限定的国王个数。
|
|
|
在满足了上面的两个条件后，就可以通过上一行和本行的状态，计算出由上一行迁移过来的方案数量。
|
|
|
|
|
|
|
|
|
#### 预处理
|
|
|
**双重循环遍历所有 合法状态 ，找出 合法状态之间的兼容关系**
|
|
|
```cpp {.line-numbers}
|
|
|
//i与i-1行之间的兼容关系记录下来
|
|
|
for (int a: st)
|
|
|
for (int b: st) {
|
|
|
//a&b==0:同列不是同时为1，表示列上面国王不冲突
|
|
|
//check(a|b)： 经或处理后的数字，如果存在连续的1，就表示斜45度有国王，不合法,妙不可言
|
|
|
if ((a & b) == 0 && check(a | b))
|
|
|
head[a].push_back(b);//记录合法的状态转移关系
|
|
|
}
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
#### $Code$
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
// 棋盘式状态压缩DP
|
|
|
typedef long long LL;
|
|
|
const int N = 12; // 棋盘的长宽上限,建议多开两个，防止溢出
|
|
|
const int M = 1 << 10; // 二进制枚举的状态数量上限，因为n最大是10,就是2^10个状态
|
|
|
const int K = 110; // 国王的个数上限
|
|
|
int n; // n*n的棋盘
|
|
|
int m; // 国王的数量
|
|
|
|
|
|
vector<int> st; // 所有合法的状态（预处理的结果）
|
|
|
vector<int> head[M]; // 某个状态兼容哪些状态（预处理的结果）,注意这个上限M，2022年8月13日曾经卡在这里2小时，被一个同学误导了
|
|
|
int cnt[M]; // 记录每种状态中的数字1个数，快速获取某行使用了多少个国王
|
|
|
LL f[N][K][M]; // 完成前i行，使用了j个国王，现在的状态是k:001010111之类，存在的是二进制对应的十进制数
|
|
|
|
|
|
// 判断数字x是不是有连续的1
|
|
|
bool check(int x) {
|
|
|
return !(x & x >> 1);
|
|
|
}
|
|
|
|
|
|
// 数字1的个数
|
|
|
int count(int x) {
|
|
|
int res = 0;
|
|
|
while (x) {
|
|
|
x = x & (x - 1);
|
|
|
res++;
|
|
|
}
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
scanf("%d %d", &n, &m);
|
|
|
|
|
|
// 1、筛选掉：同行出现连续1,保证同行不能出现连续1，表示国王不相邻
|
|
|
// 并且记录每个状态中数字1的个数是多少
|
|
|
for (int i = 0; i < 1 << n; i++) // 从啥也不摆到火力全开
|
|
|
if (check(i)) {
|
|
|
st.push_back(i); // 记录合法状态i
|
|
|
cnt[i] = count(i); // 记录合法状态i中有多少个国王（数字1）
|
|
|
}
|
|
|
|
|
|
// 双重循环遍历,找出相邻行之间的兼容关系
|
|
|
for (int a : st)
|
|
|
for (int b : st) {
|
|
|
if ((a & b) == 0 && check(a | b)) // 上下行，45度双重检查
|
|
|
head[a].push_back(b); // 记录合法的状态转移关系
|
|
|
}
|
|
|
|
|
|
// 3、DP
|
|
|
// 已经摆完了前0行，放置了0个国王，当前状态全是0，这种情况下只有全是0的状态是合法的，方案数为1
|
|
|
f[0][0][0] = 1;
|
|
|
for (int i = 1; i <= n; i++) // 枚举每一行
|
|
|
for (int j = 0; j <= m; j++) // 枚举国王个数
|
|
|
for (int a : st) { // 枚举第i行的每一种可能状态
|
|
|
for (int b : head[a]) { // a状态的所有合法前序状态
|
|
|
int c = cnt[a]; // 状态a的国王数量
|
|
|
if (j >= c) f[i][j][a] += f[i - 1][j - c][b]; // 从上一层的状态转化而来
|
|
|
}
|
|
|
}
|
|
|
|
|
|
LL ans = 0;
|
|
|
// 在填充完n行之后，将m个国王放完，每一个合法状态都是可能的解，累加起来是答案
|
|
|
for (int a : st) ans += f[n][m][a];
|
|
|
cout << ans << endl;
|
|
|
return 0;
|
|
|
}
|
|
|
``` |
