状态压缩入门

这是一篇 2018.8.14 提交的blog，现在是 2020.2.7 并且貌似快要上luogu日报了。。

我的另外一篇日报文

upd(2020.6.3) 感谢 @Thomasguo666 @nao_nao 指出错误。。如果还有写错的地方在评论区回复一下就好了/kk

1 dp

从dp的条件说起，事实上dp真正需要的条件只有三个:

• 转移方程
• 初值
• 边界条件

学过dp都知道，状态转移方程是最难的。但是这里我们要从状态说起。

2 状态

状态是一个非常玄学的东西。多数时候数组存储就可以，但有时状态数量太多，就把一个数组压缩成一个数字，通过位运算进行操作。
当然这种压缩往往只是选或者不选两种状态，状态太多了无法使用这种策略。

3 位运算

还是先从位运算说起。
计算机存储数据采用补码二进制，你现在使用的每个int(longlong)在计算机都是一串二进制码。int的大小范围是 2^{31}-1就是因为int占用了31位来存数据。但明明int有应该有32位才对啊？是因为第三十二位是用来存储符号的！你可以试一下，输出(1<<31)会是一个什么数字？（<<的定义在后面，可以等会过来尝试）

后面这些运算在计算器的程序员模式都有（或直接把c++当计算器），可以自行验证

• & 按位与运算

与普通的&&区别？这个是按位与！每一位都要进行！如果同为1则为1，不同为1则为0。比如，

9\&12 = (1001)_2 \&(1100)_2=(1000)_2=4

与运算有什么用？可以判断某一位是否为1。
比如判断k的从右数第j位是否为1 就是

if(k&(1<<j))

&一般被看作集合的交集。比如，第k位是1代表这个集合有k这个元素，第k位是0表示这个集合没有k这个元素。则一个整数就是一个集合，两个集合的交就是这两个数字并起来。这点非常有用，一定记住！
很容易证明，与运算是不升的，也就是说，一个数字不管怎么与，也不可能大于原数字。这一点有些题可以用到（对于unsigned）。
记得前段时间打cf做了一个题就是关于与运算，可以看一下：

CF1013B

• | 按位或运算
  同样类比与运算，它就是每一位都进行“或者”操作。如果这一位都是0则为0，有一个数字的这一位是1则是1。同样用刚刚那个例子 9|12 = (1001)_2 | (1100)_2=(1101)_2=13

  这个运算一般用来给集合赋值。比如把k的二进制从右第j个改成1（不管是不是1都改）就是：

k |= (1<<j);

其次，或运算经常被用于作为集合的并集。假设a,b是两个集合，那么他们的并就是a|b。这和与运算相反，也是一个非常重要的特性。
同时，或运算是不降的。也就是说，不管怎么或，也不可能产生的数字比原来数字还小（对于unsigned）。

• ^ 按位异或运算

异或运算与前面的不同了，异或运算被称为不进位加法。
两个数字对于每一位，相同为0，不同为1.
比如 9\hat{} 12=(1001)_2\hat{} (1100)_2 = (0101)_2 = 9
是不是很像不进位的加法？
异或最为重要的性质是x^y^y=x
也就是说它的逆运算为本身！
这个运算用途比较玄学，需要用心感悟

• 左移<< 右移>>

左移操作 <<

把二进制所有位向左边移一位，最低位补0，最高位移出去（消失）。多数时候跟*2等价，但是一定注意int不要移到31，这时候就会移到符号位，如果符号位为1，就变成负，符号位0，正。如果不想考虑这么麻烦，使用unsigned可以解决问题。
尝试一下输出1<<31，发现输出了-2147483648？！为什么？因为计算机存储使用补码。对于负数，补码是会与源码发生改变。不知道的自行百度，在此不再累赘。

右移操作 >>

右移操作自然就是把所有位向右移动。超出右边的会自动去掉。但是区别在于，它左边不是补0，而是补符号位。（对于unsigned不存在）。比如符号位是1，那么右移后左边补充的是1，而不是0. 这个可以当作除以二用。

• 按位取反~

这个用得非常少，就是把二进制所有位全部取反。
比如~0 = (11111....111)_2=-1
也就是说，~a=-a-1

关于位运算的优先级

这是个非常玄学的东西，实在想要搞清楚自行百度，这里不再赘述。强烈建议大家全部打上括号！！预防万一突然记错/打错。这种例子数不胜数。
另外，为了避免玄学错误，请尽量用unsigned代替int进行位运算。

4 用状态压缩dp

4.1 什么时候用？

1. 数据范围
   范围在20左右时正常的状压当然凡事有二般情况
   很多时候会有一些NP问题会用状压求解。
2. 是否可以压缩
   一般的状态压缩都是选择或者不选择，放或者不放，遇见这种东西一般时状压。八皇后问题也是一个状压的代表。
3. 常见题目模型
   比如TSP，覆盖问题之类的。经常会有这种模型的题出现就可以使用状压。

5 例题解析

TSP问题

给你n个城市和城市之间的通路的长度，找出一条经过所有城市一次且仅经过一次的路线，使得这条路线的长度最短。
因为设计路线，所以状态肯定与你现在所在的城市有关系。其次，你还需要保存经过了哪些城市（不能重复走）。如果一个城市被经过了用1表示，没有到过用0表示一个整数就可以表示所有城市是否被走过，那么可以得到dp[i][j]其中i表示当前经过和没有经过的（二进制），j表示你站在j城市。所以方程容易得到：

dp[i][j]=min\{dp[i|(1<<(j-1))][k]+w[j][k]\}

NOI2001 炮兵布阵

洛谷 P2704====传送门====

此题暴力肯定超时，怎么办呢？
因为m<=10，所以每一行的状态肯定可以表示成一个整数。还是假设放置是1，不放是0.
然后我们可以枚举一行中的所有的状态（可以打表啦），而且手推一下会发现一行状态数量是很少的。（不会超过100）
于是我们记录了所有状态的士兵数量。根据题意我们明显发现，每一行只与其前两行有关系。因此我们假设

前面说过，第i行仅仅和i-1 i-2有关系，所以列出方程： $dp[i,st1,st2]=max\{dp[i-1,st2,j]+sum[st1]\}

其中j是枚举的i-2行状态，sum代表这种状态下的数量。

下面就是状态是否可行的问题了。首先，第i行的状态肯定不可以和环境冲突啊！
第i行如果和环境冲突，那么肯定在有山的地方放了1。怎样判断比较快？输入的时候就转化成二进制。如果有山这位就是1，若果没有就是0.这个时候，如果原地形是0，则第i行状态可以是1/0，如果原来是1，则第i行必须是0.这不就是按位与运算吗？如果原地形和第i行的状态and一下后不是0，那么自然代表状态不成立（出现了两个1！）所以这里判断只需要一次与运算。

然后判断当前行和上面一行冲突是否。这里我们发现和判读地形一样，不能同为1，所以也是一遍与运算。
判断当前行与上上行，仍然是一遍与运算。

最后捋一遍思路

• 把输入的字符串变成一个整数（按照二进制转十进制）
• 枚举i（2-n）
• 枚举第i行状态
• 判断是否与地图冲突（&）
• 枚举第i-1行状态
• 判断
• 枚举第i-2行
• 判断（别忘了特判第二行！）
• dp方程。。

6 总结

近年来noip中dp考得越来越多（每年基本都有）
难度也不断上升。
作为一个dp蒟蒻 感觉dp题还是得靠多做，找感觉。
最后祝愿大家（包括我）noip2018 rp+=66666

最后宣传一下blog。
yijan.co