AC. 梦想

frank_c1

[BZOJ 1087] 互不侵犯

发布于2016年01月15日 | 暂无评论 | 697阅读 | 状态压缩

题目描述

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

输入格式

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

输出格式

方案数。

题目解析

自己写出来的第一道状压DP,鼓掌~~

注意到这题并不是n皇后问题,有一些区别,搜索是会T的。考虑状压DP,先预处理出一行中合法的状态,记一个合法状态i中King的数量为cnt[i]。可以发现N<=9时,合法状态数不会超过89个,依次编号,记状态总数为tot;接着处理出状态之间合法的转移集合S。令dp[i][j][k]表示第i行的状态编号为j且此时还可以放k个King的方案数。则

{dp[i][j][k]} = \sum\limits_{(t,j) \in S} {dp[i-1][t][k-cnt[j]]}

最终答案为\sum\limits_{i = 1}^{tot} {dp[N][i][K]}。具体实现细节详见代码。