状压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)

三(多)进制状压

Loj 10172

我们相当于把一个整数当做三进制数来看,也就是说$(25)_{10}={221}_3$,我们就维护这个$221$。
我们开一个数组sjc[状态][位]=位上的值 (0, 1, 2),用来找一个状态每一个位上是什么
这个数组可以用十进制转三进制的方法求得,具体看代码。
然后注意本题要特判$k=1,k=n$,并且只有一行的情况。

常见题型

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、三(多)进制状压
Q:Loj 10172
解:Loj 10172
例题: Loj 10172

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