状态压缩和倍增优化dp

· · 个人记录

本章主要讨论通过 优化状态设计 优化 \text{dp} 的两种常见思想方法。

\text{0x56} 状态压缩 \text{dp}

在某些题目中，我们需要用一整个大小为 n 的集合 S 描述「状态」，但如果该集合中的每个元素都是不超过 k 的自然数，那么我们就可以考虑将这个集合看作一个 n 维 k 进制数，并使用一个整数 i\in[0,k^n) 描述这一维状态。像这样将集合转化为整数并作为 \text{dp} 的一维状态的状态设计方法，称为 状态压缩，简称状压。

  1. 最短Hamilton路径\text{ / }旅行商问题\text{ / }吃奶酪

最经典的状压题型之一——最短Hamilton路径问题。使用一个 n 位二进制数 i 储存节点的访问情况，同时在附加一个维度 j 记录当前节点编号。不难得出状态转移方程：

f(i,j)=\min\limits_{k\in[0,n)}\Big\{f(i\oplus\!(1\!\ll\! j),\, k)+\operatorname{dis}(k,j)\Big\}
  1. 棋盘覆盖\text{ / }Corn Fields\text{ / }炮兵阵地

也是很经典的一类状压题型——方格填充问题。并且填充的图形仅与相邻的若干行有关，因此容易按照行号划分阶段并使用状态压缩表示各行状态，进而使用动态规划算法。一个值得注意的技巧是，可以 先根据题意的限制，预处理出所有合法的状态，以避免 \text{dp} 过程中重复无效的枚举和判断。

  1. 宝藏

这是一个较为复杂的状压 \text{dp} 问题。

但是刚开始看到这道题的时候，会感觉更像是一道搜索。已开凿的道路可以任意同行并不花费代价，因此题目所求就是让所有宝藏屋连通的最小代价。于是可以先考虑写下搜索算法：

  1. 任选一个节点为根，即为赞助商帮忙打通的宝藏屋 ；
  2. 任选一个已经打通了的宝藏屋，从它开凿一条可开发的并通往任意一个未打通的宝藏屋的道路，累加答案，然后重复这一步骤，直到宝藏屋被全部打通，更新答案。

如果在每次递归过程中都重复扫描所有已打通的宝藏屋，并尝试打通一条道路，显然会遍历相当多重复的状态，时间复杂度会相当高。为此可以做出两点限制（可视作剪枝操作）：

  1. 【优化搜索顺序剪枝】先打通浅的宝藏屋，再打通深的宝藏屋。显然这不会对最终答案造成影响。
  2. 【最优化剪枝】对于多个同一种已打通的宝藏屋的集合，只需要关心其中代价最小的那个。因为打通后续的宝藏屋所需的代价与当前已打通的宝藏屋的集合内部的连接方式无关。

但是进一步分析可以发现，第一点限制其实体现了动态规划的「阶段」，而第二点限制事实上确立了动态规划的「最优子结构」，而 n 个点被打通的情况便应该作为动态规划的一维「状态」，而这正好是状压所能解决的。设 f(i,j) 表示已经打通的宝藏屋的最大深度为 i ，且当前宝藏屋的打通状态为 n 位二进制数 j 时目前的最小代价。不难得出状态转移方程：

f(i,j)=\min\limits_{\operatorname{valid}(k,j)}\Big\{f(i-1,k)+(i\!-\!1)\times\operatorname{cost}(k,j)\Big\}

其中 \operatorname{valid}(k,j) 表示状态 k 能否在只扩展一层的条件下新开凿若干条道路转化到状态 j，若可以，则最小代价为 \operatorname{cost}(k,j)。而关于 \operatorname{valid} 和 \operatorname{cost} 等具体预处理的实现细节不再赘述，但事实上这才是本题最大的难点之一。

本题其实给了我们很多启示：首先，关于 \text{dp} 的分析很多时候可以由搜索及其优化入手，这样不仅在思考的时候会更自然，而且即使这个题不能使用动态规划，也可以为其它算法的分析铺垫很多关键的信息；其次，在设计状压 \text{dp} 的状态转移方程的时候，应适当引入一些预处理的内容，因为对于进行了状态压缩以后的状态，处理起来可能会相对复杂和麻烦，因此适当的对预处理的内容的引入可以使得状态转移方程的逻辑和设计更加自然，但同时也需要考虑预处理本身的时空和代码复杂度；最后，题目的数据范围在某种程度上也提示了状压 \text{dp} 的可行性。过大的数据范围显然会导致压缩成整数的状态使得空间溢出。

  1. Bill的挑战

这是一道稍有难度的状压 \text{dp}，除了数据范围几乎没有任何提示（大雾。突破口在于对 g 数组的引入，十分的巧妙，详见 此题解。

\text{0x57} 倍增优化 \text{dp}

倍增优化 是一种巧妙的优化思路，它将原本复杂度为 \mathcal{O}(n) 的线性递推通过预处理转化为复杂度为 \mathcal{O}(\log n) 的成倍增长式递推，个人认为 与矩阵加速递推有异曲同工之妙，很多时候无法使用，也因此很难考虑到；但是一旦在适用范围内使用，就可以达到一些超乎寻常的优化效果。

  1. 跑路

这个题作为倍增思想的一个引入。

首先我们肯定不能先求最短路再尝试二进制拆分，因为可能会有一条稍长的但是长度正好为 2 的正次幂的路径，显然会更快。因此考虑引入 C(k,i,j) 表示 i 能否在经过长度为 2^k 的路径后到达 j，若可以，在新图中将 i 和 j 连上一条长度为 1 的边。建边完成后，在新图使用一次 \text{Floyed} 求最短路即可。

  1. 开车旅行

这是一道很经典 麻烦 的题目，关键在于预处理。