浅谈状压DP

# 状态压缩入门 这是一篇 2018.8.14 提交的blog，现在是 2020.2.7 并且貌似快要上luogu日报了。。 [我的另外一篇日报文](https://www.luogu.com.cn/blog/yijan/unordered) 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 就是 ```cpp if(k&(1<<j)) ``` &一般被看作集合的交集。比如，第k位是1代表这个集合有k这个元素，第k位是0表示这个集合没有k这个元素。则一个整数就是一个集合，两个集合的交就是这两个数字并起来。这点非常有用，一定记住！ 很容易证明，与运算是不升的，也就是说，一个数字不管怎么与，也不可能大于原数字。这一点有些题可以用到（对于unsigned）。 记得前段时间打cf做了一个题就是关于与运算，可以看一下： [CF1013B](https://www.luogu.org/problemnew/show/CF1013B) - | 按位或运算 同样类比与运算，它就是每一位都进行“或者”操作。如果这一位都是0则为0，有一个数字的这一位是1则是1。同样用刚刚那个例子 $ 9|12 = (1001)_2 | (1100)_2=(1101)_2=13 $ 这个运算一般用来给集合赋值。比如把k的二进制从右第j个改成1（不管是不是1都改）就是： ```cpp 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====传送门====](https://www.luogu.com.cn/problem/P2704) 此题暴力肯定超时，怎么办呢？ 因为m<=10，所以每一行的状态肯定可以表示成一个整数。还是假设放置是1，不放是0. 然后我们可以枚举一行中的所有的状态（可以打表啦），而且手推一下会发现一行状态数量是很少的。（不会超过100） 于是我们记录了所有状态的士兵数量。根据题意我们明显发现，每一行只与其前两行有关系。因此我们假设 $dp[i,st1,st2]$为当前第i行用第st1种状态，然后i-1行用第st2种方案。转移时穷举i-2行所有的状态。 前面说过，第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](yijan.co)