锐客网

  1. 首页 > it技术 > >

#|状压DP（涉及位运算）

【简介】 状压DP是基于状态压缩的动态规划，又叫做集合动态规划。
顾名思义，这是一类以集合为状态的特殊的动态规划问题。有些时候，需要被记录到得状态有很多，但是对每个状态都开一维来记录显然是行不通的，我们就考虑把这些状态压缩一下，通常情况下，若只有两种状态，我们会把状态用二进制表示，然后把它转成十进制来记录
【#|状压DP（涉及位运算）】基于状态压缩的动态规划是一种以集合内的元素作为状态，状态总数为指数级别的动态规划，它有以下两个特点：

  1. 具备动态规划的两个基本性质，即最优化原理（最优子结构性质）和无后效性
  2. 数据规模的某一维或者几维非常小

【位运算】 状压DP会经常用到位运算，我简单介绍一下
链接位运算（百度上的讲解）
位运算会把两个数转成二进制后再计算，计算时是按位处理，即结果单独计算出来，再组成一个新数
  • 与运算&（and）：相同位都为1，则为1；若有一个不为1，则为0。 即0&0=0，0&1=0，1&0=0，1&1=1
  • 或运算|（or）：相同位只要一个为1即为1。 即0|0=0，0|1=1，1|0=1，1|1=1
  • 异或运算^（xor）：相同位不同则为1，相同则为0。 即0^0=0，0^1=1，1^0=1，1^1=0
  • 取反操作~（not）：把0和1全部取反。 即每位0变1，1变0，要注意一下它会将有符号整数的符号位也取反
  • 左移操作<<（shl）：a << b 是把二进制数a向左（高位）移b位（低位的最后b位补0）。
  • 右移操作>>（shr）：a >> b 是把二进制数a向右（低位）移b位（高位的起始b位补0）。
不难发现，若对于十进制数 x，y，那么#|状压DP（涉及位运算）
文章图片
<< #|状压DP（涉及位运算）
文章图片
= #|状压DP（涉及位运算）
文章图片
，#|状压DP（涉及位运算）
文章图片
>> #|状压DP（涉及位运算）
文章图片
= #|状压DP（涉及位运算）
文章图片
，可以根据这个干些神奇的事情
上面的东西是基础知识，下面介绍一些常用的操作（可以自己推一下，也不难理解）
  • 取出二进制数 x 的第 k 位，存在 y 中：y = 1 << k & x（或 y = x >> k & 1）
  • 取出二进制数 x 的最后一个 1（也就是 lowbit），存在 y 中：y = x & -x
  • 将二进制数 x 的第 k 位变为 1：x = x | 1 << k
  • 将二进制数 x 的第 k 位变为 0：x = x & ~（1 << k）
  • 将二进制数 x 的第 k 位取反：x = x ^ 1 << k
  • 取出二进制数 x 的最后 k 位，存在 y 中：y = x & （1 << k）- 1
  • 将二进制数 x 低位连续的 1 变为 0：x = x & x + 1
  • 将二进制数 x 低位连续的 0 变为 1：x = x | x - 1
  • 取出二进制数 x 低位连续的 1，存在 y 中：y =（x ^ x + 1）>> 1
  • 快速枚举集合 S（用二进制数 x 表示）的所有子集：for（i = x；i ! = 0；i =（i - 1）& x）
下面是各个操作的优先级（同级的是从左到右运算）
  1. ( )[ ]->.::++（后置）--（后置）
  2. !~++（前置）--（前置）-+*&( type )sizeof
  3. ->*.*
  4. */%
  5. +-
  6. <<>>
  7. <<=>>=
  8. ==!=
  9. &
  10. ^
  11. |
  12. &&
  13. ||
  14. ? :（三元运算符）
  15. =+=-=*=/=%=&=^=|=<<=>>=
  16. ,

【例题+讲解】 题目大意：有一个W行H列的广场，需要用1*2小砖铺盖，小砖之间互相不能重叠，能不能铺完整个广场？若能，输出有多少种不同的铺法；若不能，输出 -1（1≤W，H≤11）
对于这道题，用暴搜的话应该是要超时的（我也不太清楚，没试过）
首先我们考虑，若W和H都是奇数，那肯定是铺不成的（因为此时广场的面积为奇数，而小砖的面积为偶数）
剩下的情况，我们就用状压DP来做
我们用 f [ i ][ j ] 表示铺到第 i 行，状态为 j 的方案数。在DP的时候用 i 表示当前行，s1 表示当前行的状态，s2 表示下一行的状态， d 表示到了 d 这个点，DP时具体操作如下：
  • 如果点 d 没有被覆盖，那就可以竖放，并把 d 下面那个点记为覆盖了（即改变s2）
  • 如果点 d 和点 d + 1 都没有被覆盖，那就可以横放，不用改s2
  • 如果点 d 被覆盖了，直接到下一个点 d + 1
（自己画图更好理解一点）
初始化：f [ 1 ][ 0 ] = 1（即第一行没有铺过砖的方案数，显然为 1）
这样的话，最后的答案answer = f [ H + 1 ][ 0 ]（即第 H + 1 行没有铺过砖的方案数，显然就是答案）
最终的时间复杂度为O（#|状压DP（涉及位运算）
文章图片
），即O（#|状压DP（涉及位运算）
文章图片
），这样的话，我们有一个小优化，当W>H的时候，就交换W和H，相当于把矩形翻转一下，但这样会以小的数为指数，会优化一点
代码（代码中的神奇位运算操作可以去上面看，应该都有提到）：
#include #include #include using namespace std; const int N=15,M=1<<11; int w,h,state; long long f[N][M]; void dp(int i,int s1,int s2,int d) { if(d==w) f[i+1][s2]+=f[i][s1]; //如果这一行已经走完，直接累加答案 else { if(!(s1&(1<h)swap(w,h); //小优化 state=1<

【入门题目推荐】 状压DP和普通DP一样，都需要大量刷题来找感觉，这里推荐几道入门题，感兴趣的话可以做一下
POJ 3254Corn Fields
POJ 1185炮兵阵地
洛谷 1171售货员的难题

    推荐阅读


    上一篇：[转]如何学习《离散数学》（）

    下一篇：[教程] 教你简单解决邮件乱码（Mac／iPhone／iPad通用）