State Designing

概述

优化 dp 时，不止可以从转移过程入手，加速转移。有时，也可以从状态定义入手，通过改变设计状态的方式实现复杂度上的优化。

令人比较头疼的是，这类优化大多不具有通用性，即不能很套路地应用于多个题目中。因此，下文将从具体例题出发，力求提供思路上的启发，希望可以对读者有一定帮助。

例 1

题面

给定两个长度分别为 n,m 且仅由小写字母构成的字符串 A,B , 求 A,B 的最长公共子序列。 (n\le 10^6,m\le 10^3)

朴素的解法

您一眼秒了它，这不是板子吗？

定义状态 f_{i,j} 为 A 的前 i 位与 B 的前 j 位最长公共子序列，则有

f_{i,j}= \begin{cases} \max(f_{i-1,j},f_{i,j-1}) & ,A_i \neq B_j \\ f_{i-1,j-1}+1 & ,A_i = B_j \end{cases}

上述做法的时间复杂度 O(nm) ，无法通过本题。

更优的解法

我们仔细一想，发现了一个性质：最终答案不会超过 m 。

我们又仔细一想，发现 LCS 满足贪心的性质。

更改状态定义 f_{i,j} 为与 B 前 i 位的最长公共子序列长度为 j 的 A 的最短前缀长度（即将朴素做法的答案与第一维状态对调）

可以通过预处理 A 的每一位的下一个 a,b,\cdots,z 的出现位置进行 O(1) 的顺推转移。

复杂度 O(m^2+26n) ，可以通过本题。

例 2

题面

给定一个 n 个点的无权有向图，判断该图是否存在哈密顿回路。 (2\le n\le 20)

朴素的解法

看到数据范围，我们考虑状压。

设 f_{s,i} 表示从点 1 出发，仅经过点集 s 中的点能否到达点 i 。记 g 为原图的邻接矩阵。则有

f_{s, i} = \bigcap_{j\in s, j\neq i}f_{s - \left\{i\right\}, j}\cap g_{j, i} \left(i\in s\right)

时间复杂度 O(n^2 \times 2^n) ，写得好看或许能过，但是并不优美。

更优的解法

上面的状态设计中，每个 dp 值只代表一个 bool 值，这让我们觉得有些浪费。

我们可以考虑对于每个状态 s 将 f_{s,1},f_{s,2},\dots,f_{s,n} 压成一个 int，发现我们可以将邻接矩阵同样压缩后进行 O(1) 转移。

时间复杂度 O(n\times 2^n) , 可以通过这道题。

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article Marcythm, partychicken, Xeonacid
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments