RainAir
My OI Blog
RainAir
「SCOI2005」互不侵犯King

在清北学堂DP&Graph班里学到了这一题,状压DP的入门题目

题目描述

题目背景

在N×N的棋盘里面放K个King,使他们互不攻击,共有多少种摆放方案。King能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。

输入输出格式

输入格式:

只有一行,包含两个数N,K $( 1 <=N <=9, 0 <= K <= N * N) $

输出格式:

所得的方案数

样例

样例输入

样例输出

思路

看到这一题,首先就应该想到搜索和DP,显然暴力是不可取的。
则我们考虑DP。
设$ f[i][j][k] $表示到第i行第j列合法时已经摆放了$ k $个King时的方案数。
我们设$ status[i] $来记录一个二进制数来表示状态(第$ j $位为1的时候表示这一列有国王,反之则没有)。
$ cnt[i] $记录第i中情况有多少个1.
DP的话我们可以按照行进行状态压缩,这样即可得到一个状态转移方程:
$$ f[i][l][status[k]] = f[i][l][status[k]] + f[i-1][l-cnt[j]][status[j]] $$

当 $$ status[j] \& status[k] = 0, status[j] \& (status[k] << 1) = 0,status[j] \& status[k] >> 1 = 0 $$
边界情况:$ f[1][cnt[i]][i] = 1 $

代码实现

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/120
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「SCOI2005」互不侵犯King
在清北学堂DP&Graph班里学到了这一题,状压DP的入门题目 题目描述 题目背景 在N×N的棋盘里面放K个King,使他们互不攻击,共有多少种摆放方案。King能攻击到它上下左右,以及左上…
扫描二维码继续阅读
2018-02-09
标签
近期评论