动态规划之【状压DP】第1课：状压DP原理解析

动态规划之【状压DP】第1课状压DP原理解析一、如何理解状压1.什么是状压“状压”是状态压缩的简称它的核心思想可以用一句话概括用一个二进制数来表示一个集合其中每个二进制位代表集合中的一个元素是否存在0或1。2. 为什么需要“压缩”在动态规划中状态常常需要记录一组物品的“选”或“不选”、“有”或“无”。如果直接用布尔数组或集合来表示状态本身就会很复杂无法作为数组下标直接索引存储和转移也会非常低效。而“压缩”就是把这组布尔值打包成一个整数。比如一个集合包含第0个、第2个和第3个元素用二进制可以表示为1101从低位到高位对应元素0,1,2,3这个二进制数对应的十进制数13就是压缩后的状态。3. 核心操作位运算压缩后对集合的操作就变成了对整数位的位运算速度极快。常见的操作有操作含义位运算表达式判断第i个元素是否在集合中状态S(S i) 1将第i个元素加入集合S将第i个元素从集合中移除S ~(1 i)总结如何理解“状压”可以把“状压”理解为一种数据编码方式把“一组开关的状态”编码成一个数字。把“打开/关闭某个开关”对应成“将数字的某一位设为1/0”。把“判断某开关是否打开”对应成“检查数字的某一位是否为1”。这种压缩让DP可以借助数组下标和位运算高效运行用空间换取了时间的指数级增长2^n 状态这是它在小规模集合问题上强大的根本原因。二、状压DP的实现步骤状压DP状态压缩动态规划是一种利用二进制数表示状态的DP技巧。它将一个维度的信息压缩成一个整数通常用二进制位表示从而可以用位运算快速进行状态转移。常见于网格类、集合类问题当状态维度较小如行列 ≤ 20时效果显著。基本步骤状态表示用二进制串表示某一行的选择情况如1种草0不种或表示某个集合的选取情况。预处理合法状态提前计算出所有满足自身约束的状态如行内不能相邻减少枚举。状态转移根据问题约束从上一行的合法状态转移到当前行的合法状态通常用位运算判断是否冲突。边界处理第一行单独初始化。答案统计累加最后一行所有合法状态的DP值。关键细节位运算检查相邻(s (s 1)) 0判断s中是否有相邻的1。与土地兼容若土地状态a[i]中1表示可种则s合法需满足(s a[i]) s。上下行冲突(s t) 0保证上下没有相邻的1。滚动数组优化空间只需保留两行。注意事项数组大小状态数最多2^N但合法状态远小于此可预先存储。注意位运算优先级多加括号。第一行没有上一行转移时特殊处理。完整系列资料请查看专栏《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;}