动态规划之【状压DP】第3课：状压DP应用案例实践2

动态规划之【状压DP】第3课状压DP应用案例实践2互不侵犯题目描述在N × N N \times NN×N的棋盘里面放K KK个国王使他们互不攻击共有多少种摆放方案。国王能攻击到它上下左右以及左上左下右上右下八个方向上附近的各一个格子共8 88个格子。输入格式只有一行包含两个数N , K N,KN,K。输出格式所得的方案数输入输出样例 1输入 13 2输出 116说明/提示数据范围及约定对于全部数据1 ≤ N ≤ 9 1 \le N \le 91≤N≤90 ≤ K ≤ N × N 0 \le K \le N\times N0≤K≤N×N。思路分析状压DP思路棋盘大小N ≤ 9 N \le 9N≤9每行状态可以用二进制数表示1 11表示该列有国王。合法的行内状态必须没有相邻的1 11即(state (state 1)) 0。行间转移需要保证上下、左右对角都不冲突对于上一行状态last和当前行状态cur必须同时满足(cur last) 0上下不冲突(cur (last 1)) 0左上角对角线不冲突(cur (last 1)) 0右上角对角线不冲突DP 定义dp[i][j][s]表示前i行已经放置了j个国王且第i行的状态是第s种合法状态时的方案数。转移方程dp[i][j][cur] dp[i-1][j - cnt[cur]][last]其中cnt[cur]为状态cur中的国王个数且last与cur兼容。优化预处理所有合法状态sta[]及其国王数cnt[]并预处理状态之间的兼容关系ok[][]避免重复计算。答案最终答案为sum(dp[N][K][s])对所有的合法状态s求和。时间复杂度状态数S约为2 N 2^N2N中剔除非法状态最多2 9 512 2^951229512转移时枚举所有S总复杂度O ( N ⋅ K ⋅ S 2 ) O(N \cdot K \cdot S^2)O(N⋅K⋅S2)实际远小于此上限可以轻松通过。代码实现#includebits/stdc.husingnamespacestd;intn,m;// n:棋盘大小, m:国王总数(K)intsta[110],cnt[110],tot;// sta[]:合法状态, cnt[]:每个状态的国王数, tot:合法状态数boolok[110][110];// ok[a][b] 表示状态a能否转移到状态blonglongf[10][100][110];// f[i][j][s] 前i行放了j个国王,第i行状态为sta[s]的方案数intmain(){cinnm;// 1. 预处理所有合法的行内状态无相邻1for(ints0;s(1n);s){if((s(s1))0){// 行内无相邻1sta[tot]s;cnt[tot]__builtin_popcount(s);// 统计1的个数tot;}}// 2. 预处理状态间的转移关系上一行状态-当前行状态for(inti0;itot;i){for(intj0;jtot;j){intasta[i],bsta[j];if((ab)0(a(b1))0(a(b1))0)ok[i][j]true;// i状态可以转移到j状态}}// 3. 动态规划f[0][0][0]1;// 第0行不放国王状态为0空状态for(inti1;in;i){// 枚举行数for(intj0;jm;j){// 枚举已放国王数for(intcur0;curtot;cur){// 枚举当前行状态if(cnt[cur]j)continue;// 当前行放的国王数不能超过总数intccnt[cur];// 本行放的国王数for(intlast0;lasttot;last){// 枚举上一行状态if(ok[last][cur]){// 如果兼容f[i][j][cur]f[i-1][j-c][last];}}}}}// 4. 统计答案longlongans0;for(ints0;stot;s){ansf[n][m][s];}coutansendl;return0;}功能分析状态压缩将每行国王的放置情况压缩成一个二进制整数1 11表示该列有国王。合法性检查利用位运算快速判断行内是否有相邻的国王以及行间是否冲突。预处理优化将合法状态和它们之间的转移关系预先计算避免在DP中重复进行位运算提高效率。动态规划按照行顺序递推用三维数组f[i][j][s]记录方案数。最后累加第n nn行所有状态的方案数得到答案。数据类型使用long long保证不溢出最大方案数在N 9 N9N9时不超过long long范围。使用状压DP代码分析样例1N3, K2样例输入3 2输出161. 预处理合法行内状态棋盘大小N3所有可能的行状态是0~7二进制000~111。要求行内不能有相邻的1即不能有11出现。检查每个状态状态值二进制是否有相邻1合法国王数 cnt0 (000)否是01 (001)否是12 (010)否是13 (011)是0和1列否-4 (100)否是15 (101)否1和3列不相邻是26 (110)是1和2列否-7 (111)是否-因此合法状态共 5 个按枚举顺序存储索引s状态值sta[s]国王数cnt[s]00 (000)011 (001)122 (010)134 (100)145 (101)22. 预处理行间转移关系对于任意两个合法状态last和cur它们兼容即可以上下相邻当且仅当(sta[last] sta[cur]) 0上下无直接冲突(sta[last] (sta[cur] 1)) 0左上角对角线无冲突(sta[last] (sta[cur] 1)) 0右上角对角线无冲突注意左移/右移后只需考虑低N位高位自动丢弃逐对检查得到兼容表ok[last][cur]为true表示last可转移到curlast\cur012340truetruetruetruetrue1truefalsefalsetruefalse2truefalsefalsefalsefalse3truetruefalsefalsefalse4truefalsefalsefalsefalse即状态0全空可以转移到任意状态。状态1001只能转移到状态0和状态3100。状态2010只能转移到状态0。状态3100只能转移到状态0和状态1001。状态4101只能转移到状态0。3. 动态规划递推定义f[i][j][s]表示前i行共放置了j个国王且第i行的状态为sta[s]的方案数。初始化f[0][0][0] 1第 0 行虚拟空行。第 1 行计算i1从第 0 行状态0转移到第 1 行各状态要求j cnt[s]scntf[1][cnt][s]001111211311421其余f[1][j][s] 0。第 2 行计算i2对于每个当前状态cur枚举所有合法的上一行状态last满足ok[last][cur]累加f[1][j - cnt[cur]][last]。我们只关心j ≤ 2因为总国王数 K2。curcnt[cur]兼容的 lastf[2][j][cur]计算过程结果000,1,2,3,4f[2][0][0] f[1][0][*] 1f[2][1][0] f[1][1][*] 11103f[2][2][0] f[1][2][*] 00011(0:1), (1:3), (2:1)110,3f[2][1][1] f[1][0][0]f[1][0][3] 101f[2][2][1] f[1][1][0]f[1][1][3] 011(1:1), (2:1)210f[2][1][2] f[1][0][0] 1f[2][2][2] f[1][1][0] 0(1:1), (2:0)310,1f[2][1][3] f[1][0][0]f[1][0][1] 101f[2][2][3] f[1][1][0]f[1][1][1] 011(1:1), (2:1)420f[2][2][4] f[1][0][0] 1(2:1)得到第 2 行的所有非零值(j,cur)值(0,0)1(1,0)3(2,0)1(1,1)1(2,1)1(1,2)1(2,2)0(1,3)1(2,3)1(2,4)1第 3 行计算i3目标求出所有f[3][2][cur]并求和。对每个当前状态cur用第 2 行的结果转移curcnt[cur]兼容的 lastf[3][2][cur]计算过程结果000,1,2,3,4f[2][2][0]f[2][2][1]f[2][2][2]f[2][2][3]f[2][2][4] 11011 44110,3f[2][1][0] f[2][1][3] 3 1 44210f[2][1][0] 33310,1f[2][1][0] f[2][1][1] 3 1 44420f[2][0][0] 114. 最终答案将第 3 行j2的所有状态值相加f[3][2][0] f[3][2][1] f[3][2][2] f[3][2][3] f[3][2][4] 4 4 3 4 1 16因此方案总数为16。完整系列资料请查看专栏《csp信奥赛C动态规划》https://blog.csdn.net/weixin_66461496/category_13096895.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}