[BZOJ1087/Luogu1896][SCOI2005]互不侵犯King(动态规划,状态压缩)

发布于 2018-02-16  144 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1087/Luogu1896][SCOI2005]互不侵犯King(动态规划,状态压缩)

Description

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

Http

BZOJ
Luogu

Tag

动态规划,状态压缩

解决思路

设\(F[i][j][S]\)表示处理到第\(i\)行,当前摆放了\(j\)个国王,当前行状态为\(S\)的方案数,枚举上一行的合法方案累加转移即可。
为了方便,可以先预处理出某一行每一种拜访方式是否合法,以及有几个国王。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1087/Luogu1896][SCOI2005]互不侵犯King(动态规划,状态压缩)


HNCJ OIer