[洛谷P1896][SCOI2005]互不侵犯

题目

题目描述

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

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

输入输出格式

输入格式

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

输出格式

所得的方案数

输入样例

输出样例

题解

建议先食用这道题
这道题,其实也是一道模板题,只不过情况稍微复杂了一点,状态稍微难转移一点。

函数\变量名 作用
\(f[i][j][m]\) 第\(i\)行,第\(j\)个状态,放了\(m\)个国王
\(get\_one(x)\) 返回二进制数\(x\)的1的个数
\(can[i]\) 预处理合法状态
\(num[i]\) \(i\)状态有多少个1

和玉米田不同的是,这里\(f\)的第二维是第\(j\)个状态而不是状态\(j\)

预处理\(can\)以及\(f[1]\):
不能有相邻的国王,左移后若没有重叠则合法
顺便将当前状态的第一行赋值为1

后面就和玉米田差不多了,注释里只有与玉米田不同的注释

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注