【题目来源】
洛谷：P1896 [SCOI2005] 互不侵犯 - 洛谷
【题目描述】
在 \(N×N\) 的棋盘里面放 \(K\) 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 \(8\) 个格子。
【输入】
只有一行，包含两个数 \(N,K\)。
【输出】
所得的方案数
【输入样例】
3 2
【输出样例】
16
【算法标签】
《洛谷 P1896 互不侵犯》 #动态规划DP# #深度优先搜索DFS# #轮廓线DP# #状压DP# #各省省选# #2005# #四川#
【代码详解】
// 引入所有标准库头文件，方便使用各种标准库功能
#include <bits/stdc++.h>// 使用标准命名空间，避免每次使用标准库函数时都需要加 std:: 前缀
using namespace std;// 定义全局变量
int n, k; // n: 棋盘的行数，k: 需要放置的国王数量
long long f[9][1 << 9][82]; // f[i][st][j]: 动态规划数组，表示前i行状态为st且已放置j个国王的方案数
long long ans; // ans: 存储最终结果// 计算状态st中1的个数（即该状态放置的国王数量）
int c(int st)
{int cnt = 0;while (st){if (st % 2){cnt++;}st /= 2;}return cnt;
}// 检查状态st是否合法（即没有相邻的1）
bool check1(int st)
{for (int i = 0; i + 1 < n; i++){if ((st & (1 << i)) && (st & (1 << (i + 1)))){return false;}}return true;
}// 检查状态st和st2是否可以相邻（即没有相邻或重叠的1）
bool check2(int st, int st2)
{for (int i = 0; i < n; i++){if (st & (1 << i)){if (st2 & (1 << i)){return false;}else if (i + 1 < n && (st2 & (1 << (i + 1)))){return false;}else if (i - 1 >= 0 && (st2 & (1 << (i - 1)))){return false;}}}return true;
}// 主函数，程序的入口点
int main()
{// 读取输入数据：n（棋盘行数），k（需要放置的国王数量）cin >> n >> k;// 初始化动态规划数组ffor (int i = 0; i < n; i++){for (int st = 0; st < (1 << n); st++){// 如果状态st不合法，跳过if (!check1(st)){continue;}// 如果是第一行，初始化f[0][st][c(st)]为1if (i == 0){f[i][st][c(st)] = 1;}else{// 遍历所有可能的已放置国王数量jfor (int j = c(st); j <= k; j++){// 遍历所有可能的前一行状态st2for (int st2 = 0; st2 < (1 << n); st2++){// 如果状态st2不合法或与st冲突，跳过if (!check1(st2) || !check2(st, st2)){continue;}// 状态转移：f[i][st][j] += f[i-1][st2][j-c(st)]f[i][st][j] += f[i - 1][st2][j - c(st)];}}}}}// 统计所有合法状态的总方案数for (int st = 0; st < (1 << n); st++){ans += f[n - 1][st][k];}// 输出最终结果cout << ans << endl;// 程序正常结束，返回0return 0;
}
【运行结果】
3 2
16