题目描述
在 n×n 的棋盘上放 k 个国王,国王可攻击相邻的 8 个格子,求使它们无法互相攻击的方案总数。
输入格式
共一行,包含两个整数 n 和 k。
输出格式
共一行,表示方案总数,若不能够放置则输出0。
数据范围
1≤n≤10,
0≤k≤n2
输入样例
3 2
输出样例
16
tip: 可以先看注释,不懂的在看下面讲解
代码(详解)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 11, M = 1 << N , C = N * N;
int n, k; // n*n的棋盘, k个棋子
LL f[N][C][M];// 第一维表示第几行, 第二维表示从第一行到当前这行的棋子个数,第三维表示状态
int cnt[M];//用于记录状态为state是这一行的棋子个数
vector<int> legal_state; // 合法状态放到这个数组
vector<int> state_trans[M]; //状态为M时能够转移的状态存到这个数组中去
bool check(int state)// 对当前枚举的状态进行判断
{
return !(state & state >> 1);//据个例子,比如101010, 那么它右移1为为10101,相与就是000000, 则!000000为1.
//若是10110, 那么它右移1为为1011,相与就是10, 则!10为0。
}
int count(int state)
{
int res = 0;//res 用于记录state中有几个题解,比如1010中,res = 2;
for(int i = 0; i < n; i++) res += state >> i & 1;//看state转换为2进制后有几个1即为该行有几个棋子
return res;
}
int main()
{
cin >> n >> k;//输入棋盘的长和宽,都为n, 输入棋子个数k
for(int st = 0; st < 1<<n; st++) //因为总共有从 0000...000 ~ 1111...111个状态,故st从0开始, 到111.111结束(状压基础)
if(check(st)) // 判断st是否合法
{
legal_state.push_back(st); // 表示st合法,放入到合法数组中去
cnt[st] = count(st); //对st状态中的棋子个数处理
}
for(auto cur_st : legal_state)//从所有合法状态中挨个找出每个状态能够转移的状态有哪些
for(auto to_st : legal_state)//总共有这么多个状态, 所以挨个判断
if(!(cur_st & to_st) && check(cur_st | to_st)) //上下两个状态比较,先按位与,比如101 & 011 = 001, 表明相邻两行有上下挨着的棋子
//若是!(101 & 010)则是1说明上下两行不挨在一起,在看下一个, 比如101 | 010是111,表名上下两行有两个纵坐标相邻的棋子,也可以互相攻击到, 代入check函数里返回0.
// 在看101与10000, 101 & 10000 = 0, 且101 | 10000 = 10101, 代入check中返回1,说明101可以转移到10000这一状态
state_trans[cur_st].push_back(to_st); //根据上面的例子,就将10000 push 到101的转移数组中去
f[0][0][0] = 1; //对f数组初始化为1,即一个不放是一种方案
for(int i = 1; i <= n; i++) //从第一行到最后一行挨个看
for(int j = 0; j <= k; j++)//从放1个棋子到k个棋子
for(auto &state : legal_state) // 挨个找合法状态中的状态
for(auto &pre_st: state_trans[state]) // 看当前枚举到的合法状态可以找到的合法状态
if(j - cnt[state] >= 0) // 如果总棋子数大于当前这一行这一状态所放的棋子,才进行转移,否则光这一行就够了
f[i][j][state] += f[i-1][j-cnt[state]][pre_st];//将当前的答案与转移来的答案累加
LL res = 0;//res表示总方案数
for(auto state : legal_state) res += f[n][k][state];//因为最后一行的状态有lenal_state.size()个,故要都加起来
cout << res << endl;//将计算好的答案输出
return 0;
}
(一).题意
这道题就是说在一个n * n的棋盘中放k个棋子,由于每个棋子互相看不起,只要对方在自己的攻击范围内就会互相开战, 每个棋子的攻击范围是以自己为中心的周围一圈
// 1代表棋子, 2表示攻击范围
0 0 0 0 0
0 2 2 2 0
0 2 1 2 0
0 2 2 2 0
0 0 0 0 0
那么要求我们找出无法相互攻击的方案总书。
(二)思路
那么其实这道题其实题意很简单, 大体的思路就是利用状压DP,用一个二进制数表示某行内的棋子分布。
看 10001110这一状态
1表示放棋子, 0代表没有,这个状态中有4个1,表示放了4个棋子
1. 那么我们的第一步是找出所有合法的状态
10101 光看这一行, 没有另个棋子在对方的攻击范围内,说明合法
1(2) 1(2) 0 0 1
我们发现这是后有一对棋子处于对方的攻击范围内,那么他就是不合法的。
2. 找到合法状态中的每个状态可以转移的状态
比方说我们要找1001这一状态可以转移的状态
先看1000,很明显是不可以的
1(2) 2 2 1
1(2) 2 2 2
上下两个挨着是不可以转移的
还是1001, 在看0100
1(2) 2 2 1
2 1(2) 2 2
此时有1处于对方的攻击范围内,那么也不行
总上,我们找出了状态转移的两大条件:
- (1)
上下两个1不能挨着
- (2)
上下两个1的横坐标不可以相邻
那么接下来该如何实现我们的两个条件呢?其实横简单,我们看代码:
if(!(cur_st & to_st) && check(cur_st | to_st))//check函数放到下面讲
其中cur_st表示当前枚举到的合法状态 to_st表示当前合法状态准备转移的状态
if语句用来看是否能转移, 先看cur & to
上下两个状态比较,先按位与,比如101 & 011 = 001, 表明相邻两行有上下挨着的棋子
101
&011
——————
001
与下来之后, 只有上下都为1,才有值,否则都为0, 此时!以下就好了
若是!(101 & 010)则是1说明上下两行不挨在一起
101
&010
————————
000
在看下一个, 比如101010是101,表名上下两行有两个纵坐标相邻的棋子,也可以互相攻击到返回0.
101
| 101010
——————————————
101111
只要有一位为1,或下来就是1
在看101与10000, 101 & 10000 = 0, 且101 | 10000 = 10101, 代入check中返回1,说明101可以转移到10000这一状态
101 101
&10000 | 10000
———————— ————————————
00000 10101
都符合两个条件,那么可以转移
但这里我们还露了一个步骤,就是找合法状态
合法状态就是类似于101001这类的,2个1不相邻就合法,像是111011之类的就不合法,代码实现如下:
bool check(int state)
{
return !(state & state >> 1);
}
如果合法的,那么一定是10101这样间隔的,
我们只需要将10101与10101左移1为相与,下来是0的一定是合法的,此时返回!0就可以
核心思想将完了,那么我们看剩下的操作:
f[N][C][M]是一个三为数组,第一维表示第几行, 第二维表示从第一行到当前这行的棋子个数,第三维表示状态
cnt[M]用于记录状态为state是这一行的棋子个数
这里的cnt是干嘛的呢
请在看我们的状态转移方程
f[0][0][0] = 1; //对f数组初始化为1,即一个不放是一种方案
for(int i = 1; i <= n; i++) //从第一行到最后一行挨个看
for(int j = 0; j <= k; j++)//从放1个棋子到k个棋子
for(auto &state : legal_state) // 挨个找合法状态中的状态
for(auto &pre_st: state_trans[state]) // 看当前枚举到的合法状态可以找到的合法状态
if(j - cnt[state] >= 0) // 如果总棋子数大于当前这一行这一状态所放的棋子,才进行转移,否则光这一行就够了
f[i][j][state] += f[i-1][j-cnt[state]][pre_st];//将当前的答案与转移来的答案累加
看到这里我想你应该明白了,cnt是我这一行要放的棋子,那么前几行只能放k-cnt个。
此时,我们只剩下最后求cnt数组了
int count(int state)
{
int res = 0;//res 用于记录state中有几个题解,比如1010中,res = 2;
for(int i = 0; i < n; i++) res += state >> i & 1;//看state转换为2进制后有几个1即为该行有几个棋子
return res;
}
我从每一位挨个找,在加起来就好了。
这里特别注意的是我们求完了f数组后,由于最后一行的状态不止有一个,所以我们得累加起来。
以上就是本题的全部思路