动态规划之【状压DP】第2课状压DP应用案例实践1Corn Fields G题目描述农场主J o h n \rm JohnJohn新买了一块长方形的新牧场这块牧场被划分成M MM行N NN列( 1 ≤ M ≤ 12 , 1 ≤ N ≤ 12 ) (1 \le M \le 12, 1 \le N \le 12)(1≤M≤12,1≤N≤12)每一格都是一块正方形的土地。J o h n \rm JohnJohn打算在牧场上的某几格里种上美味的草供他的奶牛们享用。遗憾的是有些土地相当贫瘠不能用来种草。并且奶牛们喜欢独占一块草地的感觉于是J o h n \rm JohnJohn不会选择两块相邻的土地也就是说没有哪两块草地有公共边。J o h n \rm JohnJohn想知道如果不考虑草地的总块数那么一共有多少种种植方案可供他选择当然把新牧场完全荒废也是一种方案输入格式第一行两个整数M MM和N NN用空格隔开。第2 22到第M 1 M1M1行每行包含N NN个用空格隔开的整数描述了每块土地的状态。第i 1 i1i1行描述了第i ii行的土地所有整数均为0 00或1 11是1 11的话表示这块土地足够肥沃0 00则表示这块土地不适合种草。输出格式一个整数即牧场分配总方案数除以10 8 10^8108的余数。输入输出样例 1输入 12 3 1 1 1 0 1 0输出 19思路分析状压 DP 实现思路预处理行内合法状态我们用二进制数表示每一行的种植情况某位为 1 表示该格种草0 表示不种。总状态数为2 N 2^N2N但很多状态本身就违反了“左右相邻不能同时种草”的规则。我们可以先预处理出所有行内合法的状态即没有相邻 1 的二进制数存入一个数组valid_states。对于N ≤ 12 N \le 12N≤12合法状态的数量约为 377远小于 4096这能显著减少后续 DP 的循环次数。合法状态还需要满足另外两个条件与土地肥沃情况兼容只能在肥沃的土地输入为 1上种草所以状态中为 1 的位对应的土地必须也是 1。判断(state field[i]) state即 state 是 field[i] 的子集。行间合法上下相邻的两行不能在同一列种草即当前行状态与上一行状态按位与为 0。判断(state prev) 0。DP 定义dp[i][j]表示前 i 行且第 i 行的种植状态为valid_states[j]时的方案数。为了方便我们也可以直接用状态值作为第二维但用索引访问更紧凑。初始化dp[0][0] 1第 0 行什么都不种对应状态 0 的索引。转移对于第 i 行枚举当前行的合法状态s索引j和上一行的合法状态p索引k若(s p) 0且s与第 i 行土地兼容则累加。答案所有dp[M][j]之和。为简化求和可以多加一行第 M1 行强制该行状态为 0这样dp[M1][0]就是答案。时间复杂度预处理O ( 2 N ) O(2^N)O(2N)DP 部分O ( M ⋅ S 2 ) O(M \cdot S^2)O(M⋅S2)其中S SS为合法状态数N 12 N12N12时S ≈ 377 S\approx 377S≈377远优于直接枚举所有状态的O ( M ⋅ 2 2 N ) O(M \cdot 2^{2N})O(M⋅22N)。代码实现#includebits/stdc.husingnamespacestd;constintmod1e8;// 模数intm,n;// 行数列数inta[15];// a[i] 存储第 i 行土地的肥沃状态二进制表示intf[15][112];// f[i][s]前 i 行第 i 行状态为 s 的方案数vectorintvalid_states;// 存储所有行内合法的状态无相邻 1intmain(){cinmn;// 读入土地数据转换为每行的二进制状态for(inti1;im;i){intst0;for(intj1;jn;j){intx;cinx;st(st1)|x;}a[i]st;}// 预处理找出所有行内合法的状态无相邻 1for(ints0;s(1n);s){if((s(s1))0)// 左右没有相邻的 1valid_states.push_back(s);}// 初始化第 0 行状态为 0 有一种方案什么都不种f[0][0]1;// 动态规划i 从 1 到 m1多算一行便于统计答案for(inti1;im1;i){// 枚举第 i 行的所有合法状态for(ints:valid_states){// 检查是否与土地肥沃情况兼容if((sa[i])!s)continue;// 枚举上一行的合法状态for(intp:valid_states){// 上下两行不能在同一列都有草if((sp)0){f[i][s](f[i][s]f[i-1][p])%mod;}}}}// 第 m1 行状态为 0 的方案数即为所有合法方案的总数coutf[m1][0]endl;return0;}功能分析输入处理将每一行的土地状况0/1 序列转换为一个整数a[i]方便后续用位运算判断兼容性。预处理行内合法状态提前枚举所有2 N 2^N2N种状态筛选出没有相邻 1 的状态存入valid_states。对于N 12 N12N12合法状态仅有 377 个大幅减少 DP 循环次数。DP 数组f[i][s]存储方案数第一维 i 从 0 到 m1第二维直接用状态值作为下标大小为2 N 2^N2N。状态合法性检查土地兼容(s a[i]) ! s即s中不能包含a[i]中为 0 的位。行内合法在预处理时已经保证(s (s1)) 0。行间合法(s p) 0。转移枚举上一行所有合法状态p若与当前行状态s无冲突则累加f[i-1][p]到f[i][s]。答案统计利用多一行i m1且强制状态为 0 的技巧自动汇总所有第 m 行的合法状态避免最后再循环求和。时间复杂度预处理O ( 2 N ) O(2^N)O(2N)DP 部分O ( M ⋅ S 2 ) O(M \cdot S^2)O(M⋅S2)其中S SS为合法状态数。最坏情况12 × 377 2 ≈ 1.7 × 10 6 12 \times 377^2 \approx 1.7\times10^612×3772≈1.7×106次运算非常快。空间复杂度15 × 4096 ≈ 6 × 10 4 15 \times 4096 \approx 6\times10^415×4096≈6×104个整数很小。样例 1 详细分析结合预处理题目给出的样例1输入为2 3 1 1 1 0 1 0即牧场有 2 行 3 列第 1 行全部肥沃可种植二进制111。第 2 行只有中间列肥沃二进制010。一、预处理行内合法状态N3所有0 ∼ 7 0 \sim 70∼7的状态中无相邻 1 的有0(000),1(001),2(010),4(100),5(101)。注意3(011),6(110),7(111)都有相邻 1被排除。所以valid_states [0, 1, 2, 4, 5]共 5 个。二、确定每一行与土地兼容的状态第 1 行土地 111所有合法状态都与土地兼容因为土地全是 1。因此第 1 行可选状态仍为{0,1,2,4,5}。第 2 行土地 010只有中间列为 1所以状态必须为010的子集。在合法状态中0(000)和2(010)满足条件1(001)和4(100)含有贫瘠位5(101)也含有贫瘠位。因此第 2 行可选状态为{0,2}。三、DP 转移枚举合法状态而非全状态初始化f[0][0] 1。枚举第 1 行的状态 s1 ∈ {0,1,2,4,5}且与土地兼容均兼容枚举上一行第 0 行状态 p ∈ {0}要求(s1 p)0显然成立。所以f[1][s1] f[0][0] 1对所有 s1 成立即第 1 行每种合法状态都有 1 种方案。接着处理第 2 行i2枚举 s2 ∈ {0,2}且与土地兼容已满足再枚举上一行状态 s1 ∈ {0,1,2,4,5}要求(s2 s1)0s2 0000与任何 s1 按位与都为 0所以累加所有 5 个 s1 的 $f[1][s1] $ 1得到 $f[2][0] $ 5。s2 2010检查与 s1 的冲突s10 → 无冲突加 1s11 → 无冲突加 1s12 → 冲突010 010 ≠ 0不加s14 → 无冲突加 1s15 → 无冲突加 1总计加 4得到 $f[2][2] $ 4。最后多加一行i3强制状态为 0只有 0 能通过土地检查因为 a[3] 默认为 0枚举上一行状态 s2 ∈ {0,2}要求(0 s2)0恒成立累加 $f[2][0] f[2][2] $ 5 4 9输出 9。完整系列资料请查看专栏《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;}