跳转至

状态设计优化

概述

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

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

Example I

Problem

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

Naive solution

您一眼秒了它,这不是板子吗?

定义状态 dp_{i,j}A的前 i位与 B的前 j位最长公共子串,则有

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

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

Higher solution

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

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

更改状态定义 dp_{i,j}为与 Bi位的最长公共子序列长度为 jA的最短前缀长度(即将朴素做法的答案与第一维状态对调)

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

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

Example II

Problem

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

Naive solution

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

dp_{st,i}表示从 1出发,经过点集 st后到达 i的方案是否存在。则有

dp_{st,i}=\sum dp_{st-2^{i-1},j}\&mp_{j,i}\;\;(st\&2^{i-1} \;\&\&\; st\&2^{j-1})

其中 mp为图的邻接矩阵

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

Higher solution

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

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

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


评论