#|状压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售货员的难题

    推荐阅读