★ FEATURED ARTICLE 【题目描述】原题来自SGU 223在 n×n 的棋盘上放 k 个国王国王可攻击相邻的 8 个格子求使它们无法互相攻击的方案总数。【输入】只有一行包含两个整数 n 和 k。【输出】每组数据一行为方案总数若不能够放置则输出 0。【输入样例】3 2【输出样例】16【提示】样例输入 24 4样例输出 279数据范围与提示对于全部数据1≤n≤10,0≤k≤n^2 。一、 题意转换本题本质上是求解在一个满足特定“邻域互斥限制”即任意两个元素不能在相邻的 8 个格子中共存的棋盘上放置k个不可分辨元素的合法组合方案总数。二、 思考过程与解题思路面对这道题我们是如何一步步推导出最优解的1. 为什么第一直觉的暴力不可行如果是初学者第一直觉肯定是dfs回溯暴力搜索遍历棋盘的每一个格子枚举“放”或“不放”。 但我们算一笔物理算力的账当N 10时棋盘有 100 个格子。暴力搜索的时间复杂度是惊人的必然超时。2. 破局核心为什么一定会想到“状态压缩 DP”很多同学以为用状压是因为“数据范围小”。错数据范围小仅仅是物理算力允许我们用状压的“客观通行证”而逼着我们必须用状压的绝对核心动机是为了完整打包“历史遗留的二维形状”痛点普通标量无法传递二维信息在基础的一维 DP如打家劫舍中状态是一个“标量”例如“前i个房间偷了多少钱”。但在棋盘放国王时当你站在第i行准备放棋子你面临的不是一个点而是一条长达N个格子的战线。如果你只记录“上一行放了 3 个国王”这毫无意义——你不知道这 3 个国王是挤在左边还是散布在两边也就根本无法判断当前行的哪些格子是安全的。一整行的 0 和 1 构成的“二维形状”是约束下一行的最小信息单元绝对不能被拆散。截面理论为什么刚好压缩“一行”国王的攻击半径是 1只能打到上下左右和对角线。这意味着第i行的安危仅受第i-1行的直接威胁。这就好比拿刀切断棋盘为了保持“无后效性”你的刀刃状态记录必须足够厚厚到能挡住所有的攻击判定。因为攻击只能穿透 1 行我们把“1 整行”作为一个切面打包就完美切断了前后的联系。思考题如果是放“马”走日字会攻击到前两行这时候你的截面该有多厚答案是必须同时压缩连续的两行状压的本质降维欺骗 DP 框架不能用数组套数组f[i][ array ]那我们就把1010这样的阵型直接看作一个十进制的整数10。状压 DP 的本质就是把一整个复杂局面一行的 01 排列打包成一个二进制数强行降维成一个普通数字塞进 DP 数组的维度里。三、 算法设计与样例推演1. 状态定义设f[i][j][o]表示i当前推导到第i行。j截止到目前前i行总共放置了j个国王。o第i行采用的阵型是第o个合法状态由于合法状态不多我们对其进行了离散化编号。2. 状态转移方程f[i][j][o] 代表当前阵型o消耗了几个国王。b代表上一行所有不与当前阵型o冲突的合法阵型编号。3. 极简样例推演假设N3, K2。预处理单行不冲突的合法状态有 000(需0人), 001(1人), 010(1人), 100(1人), 101(2人) 等。推导第 1 行若采用101用2人则回头去查第 0 行用 0 人的账本方案数f[1][2][101] f[0][0][0]即为 1。推导第 2 行若第 2 行想采用010用1人它会试图继承第 1 行用 1 人的方案。但由于010和101在对角线上冲突位运算拦截生效010无法继承101留下的方案。四、 时空复杂度分析空间复杂度 状态维数为f[15][110][150]。由于N10时单行没有相邻 1 的合法状态仅有 144 个隐含斐波那契数列规律所以第三维开到 150 足矣。 总空间为byteslong long远低于题目要求的限制空间极其充裕。时间复杂度 外层N循环 10 次K循环 100 次内部两层有效状态循环。 总计算次数约为次。在 C 每秒10^8次基本运算的红线内毫无压力。复杂度严格为其中M为离散化后的合法状态数。五、 坑点与易错总结防爆long long方案总数随着N增大呈指数级上升DP 数组和最终的ans必须使用long long否则在累加过程中极易爆int变成负数。算术地基f[0][0][0] 1第 0 行放置 0 个国王是一种绝对成立的底层推导基石。如果没有这块地基点燃火种后续所有的皆为 0。位运算优先级陷阱在 C 中按位与的优先级低于逻辑等。写成i i 1 0是极其致命的会被解析成i (i 1 0)。必须严格加括号写成(i (i 1)) 0六、 代码进阶与优化剖析核心教学点虽然基础的四重循环已经足以 AC但为了应对 CSP-S 考场上可能出现的“毒瘤”卡常数据代码仍有两个高阶优化空间1. 常数优化用“邻接表”预处理合法转移对大幅降常数痛点在最内层的两重循环中每次都要做一长串位运算冲突检测。其实不管在第几行状态A能否接在状态B后面是永恒不变的。进阶在开头预处理阶段开一个vectorint valid_moves[150]提前穷举并记录所有不冲突的(A, B)状态对。最内层转移时直接写成for(int b : valid_moves[o])彻底砍掉废循环和多余判断。2. 位运算奇技淫巧__builtin_popcount替代循环数 1痛点求当前状态需要几个国王时用了for循环遍历每一位。进阶C 提供了编译器内置函数__builtin_popcount(x)它能直接在硬件指令级别 O(1)速度返回整型数字在二进制下 1 的个数代码更精简运行更极速。七、 完整代码//1.看数据范围 n最大不超过10 //所以棋盘最大不会超过100个格子 如果直接打暴力 //每个格子有放与不放两种情况 2^100肯定超时 //2.所以我们要用dp 但这道题的状态表示每个格子是否放了国王 //不太好表示 同时每一行放了几个国王毫无意义 并不能帮助解题 //但国王的攻击范围只影响相邻行 我们就可以把一整行的状态都作为一个维度 //我们发现一整行的01阵型作为一个整体传递下去 //只能选用按行转移的状压dp 将一整行的摆放情况 压缩成一个n位二进制数 //3.状态定义f[i][j][o] //代表当前判断到第i行 截止到目前总共放置了j个国王 且当前行的阵型下标为o //o是合法状态数组a的下标 a[o].id才是真实的二进制状态 //比如二进制1010代表当前行第2和第4列放置了国王 //4.状态转移f[i][j][o]Σf[i-1][j-a[o].cnt][b] //o为当前行阵型下标 //b为上一行阵型下标 a[o].cnt为当前行摆了这个阵型要花费的国王数 //5.接下来我们观察f的第三维因为n最大为102^10-11024 //第三维最大可以为1024 但是我们真的需要开这么大空间吗 //我们可以观察到10位二进制数的所有组合中 有大量相邻有1的组合 //但国王不能相邻所以我们把有相邻1的不合法状态全部删除 //所以我们把相邻有1的全部排除掉 最多也就只能有144种可能 //所以我们第三维开到150足够了 然后对所有可能进行离散化 用idx进行编号 #include iostream using namespace std; int n,k; long long f[15][110][150]; struct node{ int id;//记录合法情况二进制数本身真实的01阵型 //代表当前整数二进制表示下当前阵型包含的国王数 //当前整数二进制里1的个数 int cnt; }a[150]; int idx;//总合法情况数0-base) int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnk; //对单行所有可能的阵型进行预处理 //一行最多n个格子 所以状态上限是(1n)-1 for(int i0;i(1n);i){ //如果i自己和自己左移一位没有交集 说明不存在相邻的国王 if((i(i1))0){ a[idx].idi; //统计当前合法阵型里用了几个国王查i二进制位有几个1 //【优化批注】此处可直接改写为 //a[idx].cnt __builtin_popcount(i); 实现 O(1) 统计 for(int j0;jn;j){ if((i(1j))!0) a[idx].cnt; } idx;//当前状态信息全部录入 合法情况数1 } } //初始化 //第0行 放置0个国王 采用第0个合法状态即全0状态只有一种摆法 //因为上面的预处理是从i0开始的 所以a[0].id必然是全0状态 f[0][0][0]1; //最外层遍历行数 从第一行开始往下 for(int i1;in;i){ //遍历截止到目前这一行 一共打算放置j个国王 for(int j0;jk;j){ //枚举当前行i)采用的阵型下标o for(int o0;oidx;o){ int s2a[o].id;//s2为当前行真实的二进制阵型 int cnt2a[o].cnt;//cnt2为当前阵型所需要使用的国王数 //如果当前行的阵型所需要使用的国王数 //比截止目前总共可以使用的国王总数j都多 就直接跳过 if(cnt2j) continue; //如果当前行所需使用的国王数比国王总数少 就可以继续 else{ //枚举当前行的上一行的阵型(b) //【优化批注】若预先统计了不冲突关系 //此处可降维为 for(int b : valid_moves[o]) for(int b0;bidx;b){ //s1为当前行上一行的具体二进制表示 int s1a[b].id; //接下来要判断上一行s1和当前行s2是否有冲突 //(s2s1)0 确保当前行没有国王在上一行国王的正下方 //(s2(s11))0 确保当前行没有国王在上一行国王的左下方 //((s21)s1)0 确保当前行没有国王在上一行国王的右下方 if(((s2s1)0)((s2(s11))0)(((s21)s1)0)) //如果不冲突 就把上一行的方案数累加过来 f[i][j][o]f[i-1][j-cnt2][b]; } } } } } long long ans0; //目标n行 恰好用掉k个国王 //所以去表里把第n行 人数为k时 所有合法的阵型方案数全加起来 //就是最终答案 for(int b0;bidx;b){ ansf[n][k][b]; } coutans; return 0; }
阅读完成 · 觉得有帮助？
