状压DP/位运算 学习笔记

模板及讲解
状态压缩动态规划就是用于某种时候DP的状态难以表示时,使用二进制进行存储状态的一种动态规划。通常会用位运算进行操作:
位运算:
1、对$x$取反:~x
2、$x+1(x为偶数)$:x|1
3、$2^x$:1<<x
4、$2^{-x}$:1>>x
5、$x的对应值$(例如$0$对$1$,$2$对$3$,$8$对$9$):x^1
6、构造0~n-1位二进制数全部为1:(1<<n)-1
7、构造形如10,100,100000即[0, k-1]全部为0,[k,k]为1,这样的二进制数:1<<(k-1)

状压DP常用:
1、将a的第k位修改为1:a |= 1<<k;
2、将a的第k位修改为0:a &= ~(1<<k);
3、取第k位:a>>k & 1;
4、判定序列里有没有连续出现的1:a&(a>>1)a&(a<<1)

常见题型
1、矩阵摆放问题(第i行使用j号状态)
Q:给出一个矩阵,数为0的地方可以放置物品,且物品不可以上下左右相邻,求摆放方案数。
解:设$dp(i, st[j])$为第i行使用j状态的总方案数。
例题:poj 3254
2、矩阵摆放问题2(第i行使用j状态, 第i-1行使用k号状态)
Q:给出一个矩阵,数为0的地方可以放置物品,且物品上下左右两格之内不能有物品,求最多能摆多少。
解:设$dp(i, st[j], st[k])$为第i行使用k状态, 第i-1行使用j状态的最优解。
例题:poj 1185
3、TSP问题(S(状态)在i结束)
Q:给n+1个点,每个点的访问次数为一,求从0出发走过所有点并回到0的最短路。
解:设$dp(S, i)$为状态$i$最后访问到$j$城市的最优解。
例题:poj 3311
4、方块填充问题(第i行使用j(状态))
Q:给出n, m,求出用(1 * 2)的小方块横向竖向填充的方案数。
解:设$dp(i, j)$为第$i$行用$j$(状态)的方案总数,$j$不是编号而是状态。
例题:poj 2411
5、倒推(从1多转移到1少/使用j(状态)
Q:DP中的状态是从1多的状态转移到1少的状态。
解:从$2^n-1$开始向$1$递推,设$dp(S)$为用$S$(状态)的方案总数。
例题:zoj 3471

------ 本文结束 ------