0x58 数据结构优化 DP

状态压缩 DP 和倍增 DP 都是从状态表示入手对 DP 进行的优化。当状态表示和状态转移方程确定后，如何高效地按照公式执行计算也是一个非常值得探讨的问题。从本节开始，我们将从转移入手，探讨 DP 程序实现中的优化手段。

在0x04节的例题“BestCowFences”、0x51节的例题“LCIS”中，我们已经接触到了对于状态转移的优化。这两道题目的动态规划算法在转移时，都需要枚举一个决策，在所有可能情况中取最大或最小值。然而，随着DP阶段的增长，该决策的取值范围的下界不变，上界每次增大1。更一般地，只要这个决策的候选集合只扩大、不缩小，我们就可以仅用一个变量维护最值，不断与新加入候选集合的元素比较，即可直接得到最优决策，O(1)地执行转移。

在更复杂的情况下，我们就要用更加高级的数据结构（而不是仅仅一个变量）维护DP决策的候选集合，以便快速执行插入元素、删除元素、查询最值等操作，把朴素的在取值范围中枚举决策的时间优化为维护数据结构的时间。这就是本节探讨的主要内容。

【例题】Cleaning Shifts POJ2376/POJ3171

有一条很长的白色纸带, 被划分成一个个长度为 1 的网格, 其中第 $L$ 到第 $R$ 个网格不慎被染上了黑色墨水。现在有 $N$ 条贴纸, 第 $i$ 条贴纸可以覆盖第 $a_{i}$ 到第 $b_{i}$ 个格子, 售价为 $c_{i}$ 。求用若干条贴纸覆盖纸带上的第 $L$ 到第 $R$ 个格子, 至少要花费

多少钱。 $1 \leq N \leq 25000$ ， $1 \leq L \leq R \leq 10^{6}$ 。

设 $f[x]$ 表示覆盖 $[L, x]$ 需要花费的最小代价。

把所有贴纸按照右端点 $b_{i}$ 递增排序，按顺序扫描这些贴纸。设当前贴纸为 $[a_{i}, b_{i}]$ ，价格为 $c_{i}$ 。状态转移方程为：

初值： $f[L - 1] = 0$ ，其余为负无穷。目标： $\min_{b_i\geq R}\{f[b_i]\}$

在这个状态转移方程中，需要查询 $f$ 数组在 $[a_i - 1, b_i]$ 上的最小值，同时 $f$ 数组会不断发生更新。这是一个带有修改的区间最值问题，使用线段树维护 $f$ 数组即可在 $O(\log N)$ 的时间内执行查询、更新操作。对线段树和区间最值问题不熟悉的读者请回顾0x43节。

本题中网格位置的坐标都很小，可以直接在 $[L - 1, R]$ 上建立线段树。当坐标较大时也可以先离散化，再用线段树求解。另外，请读者在程序实现时，注意处理贴纸左、右端点超出 $[L, R]$ 的边界情况。

【例题】The Battle of Chibi HDOJ5542

给定一个长度为 $N$ 的数列 $A$ , 求 $A$ 有多少个长度为 $M$ 的严格递增子序列。 $1 \leq M \leq N \leq 1000$ , 序列 $A$ 中的数的绝对值不超过 $10^{9}$ 。因为答案可能很大, 你只需要输出对 $10^{9} + 7$ 取模后的结果。

设 $F[i,j]$ 表示 $A$ 的前 $j$ 个数构成的以 $A_{j}$ 为结尾的数列中，长度为 $i$ 的严格递增子序列有多少个。

在上式中， $i$ 和 $j$ 都可看作“阶段”，只会从小往大转移。 $k$ 是DP的“决策”，有两个限制条件 $k < j$ 和 $A_{k} < A_{j}$ 。我们先写出枚举 $k$ 的朴素程序：

const int mod = 100000007;  
memset(f, 0, sizeof(f));  
a[0] = -(1 << 30); // -INF  
f[0][0] = 1;  
for (int i = 1; i <= m; i++)  
    for (int j = 1; j <= n; j++)  
        for (int k = 0; k < j; k++)

if  $(a[k] <   a[j])$ $f[i][j] = (f[i][j] + f[i - 1][k])\% mod;$  int ans  $= 0$  .   
for (int i  $= 1$  ;i  $<   = n$  ;i++) ans  $=$  (ans  $^+$  f[m][i])  $\%$  mod;

在内层循环 $j$ 和 $k$ 进行时，可以把外层循环变量 $i$ 看作定值。我们可以发现，当 $j$ 增加1时， $k$ 的取值范围从 $0 \leq k < j$ 变为 $0 \leq k < j + 1$ ，也就是只多了 $k = j$ 这1个新决策。所以，我们需要维护一个支持如下操作的决策候选集合，其中每个决策可以用一个二元组 $(A_k, F[i - 1, k])$ 来存储：

1. 插入一个新的决策。具体来说，在 $j$ 增加 1 前，把 $(A_{j}, F[i - 1, j])$ 加入集合。

2. 给定一个值 $A_{j}$ ，查询满足 $A_{k} < A_{j}$ 的二元组对应的 $F[i - 1, k]$ 的和。

若把二元组的 $A_{k}$ 看作关键码， $F[i - 1, k]$ 看作权值，这就是一个典型的支持插入、查询前缀和的数据结构问题，用平衡树可直接解决。

当然，因为平衡树实现难度较高，我们可以把数列 $A$ 中的所有数值离散化到 $[2, N + 1]$ 之间，设 $\operatorname{val}(x)$ 表示 $x$ 离散化后的值。特殊地，我们令 $A_0 = -\infty$ ， $\operatorname{val}(A_0) = 1$ 。然后在 $[1, N + 1]$ 上建立树状数组，起初所有值为零。

1. 对于插入决策的操作，就把 $\operatorname{val}(A_k)$ 位置上的值增加 $F[i - 1, k]$ 。

2. 对于查询操作，就在树状数组中计算 $[1, \mathrm{val}(A_j) - 1]$ 的前缀和。

综上所述，我们简单地使用树状数组来维护前缀和，就把动态规划的时间复杂度优化到了 $O(MN\log N)$ 。

for (int i = 1; i <= m; i++) {  
    memset(c, 0, sizeof(c)); // c为存储树状数组数据的数组  
    add(val(a[0]), f[i-1][0]); // 树状数组add操作  
    for (int j = 1; j <= n; j++) {  
        f[i][j] = ask(val(a[j]) - 1); // 树状数组ask操作  
        add(val(a[j]), f[i-1][j]); // 树状数组add操作  
    }  
}

本节提到的三个问题是循序渐进的。这些题目中DP决策的取值范围都可以用简单的不等式来表示。在开头提到的题目中，不等式只有上界变化，且只增大不减小，于是我们采用变量维护法。在第一道例题中，不等式除上界不断增大外，下界变化没有什么规律，此时我们采用了更加灵活的支持区间最值维护的数据结构。在第二道例题中，取值范围有两个限制条件，一个是关于“数组下标”的位置，一个是关于“数列 $A$ 的数值”的位置，它们实际上是两种“坐标”。DP循环顺序保证了第一个条件的满足。对

于第二个条件，我们在“数列 $A$ ”这个“坐标轴”上建立了以 $F$ 数组中的状态为值的数据结构。

总而言之，无论DP决策的限制条件是多是少，我们都要尽量对其进行分离。多维DP状态在执行内层循环时，把外层循环变量看作定值。状态转移取最优决策时，简单的限制条件用循环顺序处理，复杂的限制条件用数据结构维护，注重二者之间的配合。在更难的题目中，还经常出现数据结构之间的嵌套，以同时满足更多的限制条件。