核心内容摘要
燃情仲夏，品鉴“青娱乐”的无限风情
信奥赛C提高组csp-s之状压DP详解及编程实例
状态压缩DP的核心思想状态压缩动态规划简称状压DP是一种利用二进制位运算压缩状态空间的动态规划方法。
适用于状态维度较高但每个维度状态数较少的场景如每个位置只有选/不选两种状态。
核心知识点状态表示用整数的二进制位表示状态例如mask0b101表示第
3个位置被选中常用位运算(s(k-
)1// 检查第k位是否为1s|(1(k-
)// 设置第k位为1s~(1(k-
)// 设置第k位为0s1s2// 检测状态冲突__builtin_popcount(s)// 统计1的个数GCC状态设计dp[i][mask]通常表示前i行/位置且当前状态为mask时的最优解在算法竞赛中位运算的巧妙使用可以极大提升代码效率和简洁性。
以下是一些实用的小技巧和原理说明基础但关键的技巧判断奇偶性if(n
// 等价于 n % 2 1原理二进制最低位为1时是奇数交换两个数a^b;b^a;a^b;// 无需临时变量原理利用异或的自反性a ^ a 0取相反数intnegative~n1;// 等价于 -n原理二进制补码表示法进阶状态处理技巧快速获取最低位的1intlowbitx(-x);// 示例0b10100 - 0b100应用树状数组核心操作遍历所有子集for(intsubsets;subset;subset(subset-
s){// 处理subset}示例s0b101时遍历顺序 0b101→0b100→0b001统计二进制中1的个数intcount__builtin_popcount(n);// GCC内置函数intcountbitset32(n).count();// C标准库状压DP中的黑科技快速判断相邻位冲突if(s(s
)// 检测是否有相邻的1应用棋盘类问题如互不侵犯枚举合法状态转移// 筛选有效状态示例vectorintvalid;for(ints0;s(1n);s){if(s(s
)continue;// 排除相邻1valid.push_back(s);}快速状态合法性验证// 检查状态s是否与掩码mask匹配boolvalid(s|mask)mask;性能对比表操作常规方法位运算方法加速比判断奇偶n%2 1n13x统计1的个数循环统计__builtin_popcount10x子集遍历递归生成位运算递减5x相邻冲突检测逐位比较位移与位与8x
经典模型与例题分析1洛谷P1879 [USACO06NOV]Corn Fields G难度普及/提高代码实现#includebits/stdc.husingnamespacestd;constintMOD1e8;intm,n;intfield[15];// 存储每行的土地状态二进制压缩intdp[15][112];// dp[i][s] 表示第i行状态为s时的方案数intmain(){cinmn;for(inti1;im;i){intstate0;for(intj0;jn;j){intx;cinx;state(state
|x;// 将土地状态压缩为二进制}field[i]state;}dp[0][0]1;// 初始化for(inti1;im;i){for(ints0;s(1n);s){if((sfield[i])!s)continue;// 状态s必须全部在肥沃格子上if(s(s
)continue;// 状态s自身不能有相邻的1for(intprev0;prev(1n);prev){if((sprev)
{// 上下两行状态不冲突dp[i][s](dp[i][s]dp[i-1][prev])%MOD;}}}}intans0;for(ints0;s(1n);s)ans(ansdp[m][s])%MOD;coutans;return0;}功能模块分解
输入处理与状态压缩功能将每行的土地状态0/1转换为二进制整数。
代码片段for(inti1;im;i){intstate0;for(intj0;jn;j){intx;cinx;state(state
|x;}field[i]state;}说明将每行的输入例如1 0 1压缩为二进制整数如0b101即十进制5。
field[i]表示第i行的合法土地掩码。
动态规划初始化功能初始化虚拟的第0行状态。
代码片段dp[0][0]1;说明第0行是虚拟行表示没有放置奶牛此时方案数为1空状态。
状态转移功能逐行枚举所有可能的状态并检查合法性。
代码片段for(ints0;s(1n);s){if((sfield[i])!s)continue;// 必须全部在肥沃格子上if(s(s
)continue;// 同一行不能有相邻的1for(intprev0;prev(1n);prev){if((sprev)
{// 上下两行不能有相邻的1dp[i][s]dp[i-1][prev];}}}关键检查条件土地合法性状态s的二进制位必须全为肥沃土地即s是field[i]的子集。
行内无冲突状态s的二进制位不能有相邻的1通过s (s
检测。
行间无冲突当前行状态s与上一行状态prev不能有上下相邻的1通过s prev 0检测。
结果汇总功能统计最后一行的所有合法状态的总方案数。
代码片段intans0;for(ints0;s(1n);s)ans(ansdp[m][s])%MOD;说明将所有可能的最终状态累加得到总方案数。
关键算法分析状态压缩每行的状态用二进制数表示例如0b101表示第
3列放置奶牛。
状态总数最多为 ( 212 ^{12}12 4096 )适合动态规划。
合法性检查行内检查通过s (s
快速判断是否有相邻的1。
土地适配检查通过(s field[i]) s确保所有放置位置都是肥沃土地。
示例验证假设输入为2 3 1 1 1 1 1 1可能的合法状态第1行0b000空、0b
0b
0b
0b101。
第2行需与第1行状态不冲突。
最终总方案数为 17。
经典模型与例题分析2洛谷P1896 [SCOI2005]互不侵犯难度普及/提高问题描述在N×N的棋盘放置K个国王要求任意两个国王不互相攻击。
代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;ll dp[10][1024][90];// dp[i][mask][cnt]intn,k;vectorintvalid_states;// 检查单行合法性boolcheck(ints){return!(s(s
)!(s(s
);}// 生成所有合法行状态voidpreprocess(){for(ints0;s(1n);s){if(check(s))valid_states.push_back(s);}}intmain(){cinnk;preprocess();// 初始化第一行for(autos:valid_states){intcnt__builtin_popcount(s);if(cntk)dp[0][s][cnt]1;}// 状态转移for(inti1;in;i){for(autocur:valid_states){intcnt_cur__builtin_popcount(cur);for(intprev:valid_states){if((curprev)||(cur(prev
)||(cur(prev
))continue;for(intc0;ck-cnt_cur;c){dp[i][cur][ccnt_cur]dp[i-1][prev][c];}}}}// 统计答案ll ans0;for(autos:valid_states)ansdp[n-1][s][k];coutans;return0;}功能模块详解
数据结构定义dp[10][1024][90]三维动态规划数组维度含义第一维处理到第i行棋盘共n行i ∈ [0, n-1]第二维当前行的状态压缩值mask最大状态数为2^9 512但合法状态更少第三维已放置的国王总数cnt最多k个值表示当前状态下的合法方案数。
valid_states存储所有单行合法的状态二进制无相邻1。
预处理合法状态check(int s)检查单行状态s是否合法!(s(s
)!(s(s
若s的二进制位有相邻的1如0b110则返回false。
preprocess()遍历所有可能的单行状态s ∈ [0, 1n)筛选出合法状态存入valid_states。
初始化第一行for(autos:valid_states){intcnt__builtin_popcount(s);if(cntk)dp[0][s][cnt]1;}对每个合法状态s计算其包含的国王数量cnt即二进制中1的个数。
若cnt ≤ k则在第一行放置该状态的方案数为1。
状态转移for(inti1;in;i){for(autocur:valid_states){// 当前行状态intcnt_cur__builtin_popcount(cur);for(intprev:valid_states){// 前一行状态// 检查纵向和斜向冲突if((curprev)||(cur(prev
)||(cur(prev
))continue;// 遍历可能的国王数量for(intc0;ck-cnt_cur;c){dp[i][cur][ccnt_cur]dp[i-1][prev][c];}}}}冲突检测cur prev检查上下相邻列是否有冲突。
cur (prev
检查当前行与上一行左移一位后的斜向冲突。
cur (prev
检查当前行与上一行右移一位后的斜向冲突。
状态转移若状态无冲突则将前一行prev状态下已放置c个国王的方案数累加到当前行cur的c cnt_cur位置。
结果统计ll ans0;for(autos:valid_states)ansdp[n-1][s][k];coutans;遍历最后一行的所有合法状态s累加已放置k个国王的方案数。
关键设计思想状态压缩将每行的状态用二进制数表示1表示放置国王将指数级的状态空间压缩到多项式级别。
合法状态筛选预处理所有单行合法状态减少无效状态转移。
三维状态设计dp[i][mask][cnt]精确记录行数、当前行状态、总国王数三个维度确保转移无遗漏。
复杂度分析时间复杂度( O(n⋅ S 2 ⋅ k \cdot S^2 \cdot k⋅S2⋅k) )其中 ( S ) 为合法状态数约60。
当 ( n9, S≈60, k81 ) 时计算量约为 (9 ⋅ 60 2 ⋅ 81 ≈
6 × 10 6 9 \cdot 60^2 \cdot 81 ≈
6 \times 10^69⋅602⋅81≈
6×
完全可接受。
空间复杂度( O(n⋅ S ⋅ k \cdot S \cdot k⋅S⋅k) )当 ( n9, S60, k81 ) 时占用约 ( 9⋅ 60 ⋅ 81 ⋅ \cdot 60 \cdot 81 \cdot⋅60⋅81⋅8B ≈ 349KB )。
优化思考滚动数组优化由于当前行只依赖前一行可将dp数组压缩为二维dp[2][S][k]将空间复杂度降至 ( O(S⋅ k \cdot k⋅k) )。
剪枝优化在状态转移时若c cnt_cur k可直接跳过减少无效计算。