状压 DP 基础

DP 状压DP

写在前面的话

没啥好写的...

DP状态

状压 DP 要求我们记录每一种决策的具体信息，常见的是用一个 $2$ 进制数表示，其中第 $i$ 位的 $0/1$ 分别表示在 $i$ 处不进行/进行该项决策。

大力出奇迹

常见的状压 DP 数据范围都很小，所以可以暴力存储这些状态然后大力转移。在转移的过程中常用一些位运算的技巧进行优化。

几个小技巧：

枚举一个数二进制中所有的 $1$ ：用 $lowbit$ 去找，比大力遍历优化 $\frac {1}{2}$ 的常数。
枚举一个状态的所有子集：

for(int i=1;i<1<<n;i++)
for(int j=i;j;j=i&(j-1))

考虑一个状态 $S=110011$ 每次与 $S$ 相当于忽略了 $S$ 中所有的 $0$
这样每次 $-1$ 就是大力遍历了，显然不重不漏，达到最优复杂度 $O(3^n)$

检验真理的唯一标准

例 1

有 $n$ 个物品和 $m$ 个包。物品有重量，且不可被分割；包也有各自的容量。要把所有物品装入包中，至少需要几个包。

$n \leq 24,m \leq 100$

乍看起来 $m$ 很大，无法枚举决策情况，不过显然如果要用包就用尽可能大的包比较优。
这样的话按照包的容量排序，只要记录用了几个包和目前最后一个包的剩余容量就可以确定目前的状态了。

$f_i,g_i$ 分别表示装物品状态为 $i$ 时的最少用包数和最后一个包的剩余空间。

每次选择一个不在包里的大力放进去转移即可。
这个过程是 $O(n\cdot 2^n)$ 的，比较卡常，用 $lowbit$ 转移就是$O(n\cdot 2^{n-1})$ 的了。

跑的飞快。

例 2

给出一个长度为 $n$ 的 $01$ 序列，初始均为 $0$，给出 $k$ 个位置，要求最终状态中它们为 $1$，其余为 $0$，有 $L$ 种操作方式，均为将任意一给定长度的区间状态取反，问可否达成目标状态，若可以，最小化操作次数。

$n \leq 10000，k \leq 10 ， L \leq 100$

$n$ 小一点的话随便状压可以做，不过 $n$ 太大了。
发现最终状态有很多连续的区间，都没有用，修改区间也是连续的，所以考虑差分一下前缀异或序列。

这样得到的答案状态最多和 $2k$ 个位置有关，可以状压了。
通过预处理出将长度为 $len$ 的区间取反的每个 $len$ 的最小费用去优化转移，这是一个类似背包和 BFS 的过程。

然后 DP ，每次枚举两个位置取反，这样的复杂度是 $O(2^n \cdot n^2)$ 的。写记忆化会比较容易。
复杂度不太优雅，实际上直接大力转移 $lowbit$ 即可，因为最终状态肯定都要消掉，且消的顺序没有影响，所以钦定消最低的一个不影响最优解。

BZOJ 3003 LED
原题好像是 CF 的，不记得出处了。