动态规划-状压类-总结

状压类的题，一般都需要用到二进制的性质。（用到组合数概率也不小）

母题2：

考虑用二进制表示摆放方式，然后使用位运算判断攻击。

变式

有一位很小，状压，状态类似于母题。

变式2

有交换操作，所以与逆序对相关，然后数学讨论一下，再状压。

变式3

考虑用集合、余数表示，注意只需要考虑在尾部加什么。

4

记录最后选的是什么和集合，然后处理一下关系加分。

5

贪心的考虑，选就选最大的，禁止最差的=不禁止，

6

预处理重量、花费，直接开一维表示集合，然后要用到 \(O(3^n)\) 枚举子集。

7

钦定从状态中最小的标号点出发到达某个点经历的链数，然后注意顺时针/逆时针两种。

8

给定一张无向图，去掉任意条边后，使得每个子图都是团。（团中点两两有边）

枚举子集，然后判断这些点是否满足要求（预处理）。

9

拟定我们是按照顺序放的，最后除以阶乘即可。记录选到第几组、当前组包含的人的集合、总选择的人集合。直接考虑放在这个集合、新开集合。

注意还需保证每组内编号单调。

10

横确定，竖就确定。我们只考虑横的。考虑按列处理，有点类似于插头DP，枚举分界位置，然后考虑不能有重复覆盖、无法用竖的覆盖，分别用位运算。

11

先预处理需要的亮亮最短路，然后就是常规的类似于 \(4\)，注意尽量用刷表法，填表法不方便判断从哪里转移过去的。

12

容易想到爆搜，但是会超时。于是发现可以简单的用个记忆化搜索，还恰好是个状压。

13

记录子集可拼凑出的10以内的数集，我们由于要凑十，所以可以在状态中省去超过10的部分，转移时若超过10我们可以一类处理。

14

类似于13，但是处理的是差值。

15

14套一个容斥。

规律

枚举子集可能用到（设状

态为 \(S\)，子集为 \(T\)，先令 \(T=S\)，然后不断 \(T=(T-1)\&S\)）。

往往记录的是集合、最后的选择（也可能是题目中的属性，也可能只记录一个然后枚举子集）。

可能要钦定上升、最小编号，避免算重。

还有部分小技巧（贪心、组合数、二进制）。

确定关系。

考虑刷表法/填表法二者哪个好实现或者更快。

状压可能和其他DP类型交织。

复杂度无法接受时，应当考虑去除冗余状态。