LOJ 10170 -「一本通 5.4 例 1」骑士

题面

题目传送门

在 $N*N$ 的棋盘上放 $K$ 个国王,国王可攻击相邻的 $8$ 个格子,求使它们无法互相攻击的方案总数。

思路

状压 DP 的模板,以前 DP 技能一直没怎么点,现在数据结构什么的都差不多了,开始补 DP。

预处理

对于每一行来说,我们可以用二进制来表示当前这一行的放置状态。然后再压成十进制。

然后预处理出对于一行来说的所有状态(dfs)。

用 $s[i]$ 表示对于一行的第 i 种状态, $t[i]$ 表示这种状态用掉多少个棋子。

用 $f[i][j][k]$ 表示第 i 行,状态为 j,总共(包括之前)用了 k 个棋子的方法数。

然后用位运算来判断前后两行是否合法,转移就好了。

代码

 

暂无评论

发送评论


				
上一篇
下一篇