Luogu P1896 [SCOI2005]互不侵犯 题解

Describe

题目链接

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

注:数据有加强(2018/4/25)

1 <=N <=9, 0 <= K <= N * N

Solution

状压DP。

判断两个国王是否相互干扰:$i\&j||(i<<1)\&j||i\&(j<<1)$。

设$f[i][j][k]$表示第$i$行状态$j$,布置了$k$个国王的方案数。

$$f[i][j][k]+=f[i][p][k-sum[j]]$$

Code

暂无评论

发送评论 编辑评论


				
上一篇
下一篇