决策单调性优化 DP

本文参考了这篇博客进行写作。下文的“优”均代指更小。

四边形不等式

定义：设 $cost(i, j)$ 为代价函数，那么其满足四边形不等式，当且仅当 $\forall a \le b \le c \le d, cost(a, c) + cost(b, d) \le cost(a, d) + cost(b, c)$，即"交叉优于包含"。

优化部分 1D/1D DP

考虑 DP：$f_i = \min\{f_j + cost(j, i)\}$。以下设 $p_i$ 为 $f_i$ 的最优转移点（如果有多个则强制钦定是最左 / 最右的）。

• 有结论：若 $cost$ 满足四边形不等式，则 $f_i$ 满足决策单调性（即 $p_1, p_2, \dots, p_n$ 递增）。

  证明考虑反证，假设存在 $a, b, c, d$ 满足 $a < b < c < d$，$p_c = b, p_d = a$。那么据此显然有：

  $f_a + cost(a, d) \le f_b + cost(b, d)\\ f_b + cost(b, c) \le f_a + cost(a, c)\\ f_a + cost(a, d) + f_b + cost(b, c) \le f_b + cost(b, d) + f_a + cost(a, c)\\ cost(a, d) + cost(b, c) \le cost(b, d) + cost(a, c)\\$

  如果取小于号则直接与四边形不等式矛盾，否则与强制钦定最左 / 最右矛盾。

  从此证明中也可以看出，我们实际上并不关心在 DP 中只与 $i$ 或 $j$ 有关的部分。

那么根据决策单调性，我们接下来会有多种解决方式。

分治优化

直接设 $\mathrm{solve}(l, r, L, R)$ 表示 $L \le p_l, p_r \le R$ 的转移。直接设 $mid = \lfloor\frac{l+r}2\rfloor$，暴力找到它的转移点 $p_{mid}$，递归到 $\mathrm{solve}(l, mid - 1, L, p_{mid}), \mathrm{solve}(mid + 1, r, p_{mid}, R)$ 即可。每层中 $r - l + R - L$ 总和是 $O(n)$ 的，那么总转移次数是 $O(n \log n)$。但是由于要先找到 $mid$ 的转移点，所以只能做到离线而不是半在线。

顺带一提，若 $cost$ 不能快速维护，那么用类莫队的方法移动指针时，总移动次数也是 $O(n \log n)$ 的。应该也可以支持回滚。

二分栈优化

考虑直接从左到右扫，并维护合法的转移点。由于有决策单调性，那么我们新加入一个转移点时一定是只有一个后缀可能被更新。那么我们直接考虑颜色段均摊。维护一个三元组 $(l, r, o)$ 的栈，其中一个三元组表示 $\forall i \in [l, r], p_i = o$。那么我们初始向栈中插入 $(1, n, 1)$，然后依次插入转移点 $2 \sim n$。当插入一个转移点时，栈顶的一个三元组要么被完全干掉，要么被干掉一部分，具体是哪种情况可以直接判断。如果是后者，还需要二分出具体的分界点（有时代价函数特殊时可以不需要二分）。总转移次数也是 $O(n \log n)$，是半在线的。

wqs 二分优化

有时我们还对转移的次数有限制，即 $f_{i, k} = \min\{f_{j, k - 1} + cost(j, i)\}$。

• 有结论：若 $cost$ 满足四边形不等式，则 $f_{n, k}$ 关于 $k$ 是凸的。

  考虑证明 $f_{n, k - 1} + f_{n, k + 1} \ge 2f_{n, k}$（这里是下凸，上凸也是同理）。考虑 $f_{n, k - 1}$ 的过程中有 $k$ 个转移点，$f_{n, k + 1}$ 有 $k + 2$ 个。那么后者一定有两个相邻的转移点在前者的同一段中。假设前者的对应那段是 $[l, r]$，后者的两个转移点对应的一段是 $[x, y]$，那么一定有 $l < x \le y < r$。

  考虑构造两个划分为 $k$ 段的方案，具体地，将 $x$ 对应的转移点从 $f_{n, k + 1}$ 挪到 $f_{n, k - 1}$ 中。设这两段的答案和为 $sum$，那么 $sum \ge 2f_{n, k}$，所以我们只需要证明 $f_{n, k - 1} + f_{n, k + 1} \ge sum$ 即可。将两边共同部分消掉，那么会剩下一个 $cost(l -1, r) + cost(x - 1, y) \ge cost(l - 1, y) + cost(x - 1, r)$，我们发现这就是四边形不等式。

那么我们可以直接 wqs 二分出斜率，然后每次都跑一遍二分栈即可，这样我们就以多一个 $\log$ 的代价解决了次数的限制。

优化区间 DP

考虑 DP：$f_{l, r} = \min\{f_{l, k} + f_{k, r} + cost(l, r)\}$，以下设 $p_{l, r}$ 为 $f_{l, r}$ 的最优转移点（如果有多个则强制钦定是最左 / 最右的）。

• 有结论：如果 $cost$ 满足 $\forall a \le b \le c \le d, cost(b, c) \le cost(a, d)$（即“小区间优于大区间”）且满足四边形不等式，那么 $f_{l, r}$ 也满足四边形不等式。

  证明比较复杂，大概是讨论 $p_{a, d}$ 的位置，这里就省略了。

• 有结论：如果 $f$ 满足四边形不等式，那么有 $p_{l, r - 1} \le p_{l, r} \le p_{l + 1, r}$。

  考虑固定 $r$，令 $g(l, k) = f_{l, k} + f_{k, r} + cost(l, r)$，那么 $g$ 也满足四边形不等式，因为同时和 $l, k$ 都有关的部分 $f_{l, k}$ 也满足四边形不等式。那么 $k$ 对 $l$，$l$ 对 $k$ 都有决策单调性，可以得出 $p_{l, r} \le p_{l + 1, r}$。翻转过来也可以得出另外一个不等号。

那么按层数枚举即可，每一层枚举转移点的总和是 $O(n)$ 的，总转移次数就是 $O(n^2)$ 的。

反四边形不等式

类比四边形不等式，将其中的不等号反过来，即"包含优于交叉"。

我们考虑四边形不等式实际上是证明了所有区间 $[p_i, i]$ 不出现包含情况，那么我们直接套用上述证明过程即可得到所有区间 $[p_i, i]$ 不出现交叉（相交但不包含）情况。

二分栈优化

定义 $pos(i, j)$（$i < j$）为一个 $k$，其中对于 $[j + 1, k]$ 都满足 $j$ 作为转移点更优，对于 $[k + 1, n]$ 都满足 $i$ 作为转移点更优。由于 $cost$ 满足反四边形不等式，所以一定存在这样的 $k$，并且我们可以二分出它。

考虑维护一个转移点构成的栈，同样是依次加入转移点。那么当我们加入 $i$ 时，令栈顶为 $tp$，次栈顶为 $sp$，若 $pos(tp, i) \le pos(sp, tp)$，那么 $tp$ 就被 $sp$ 与 $i$ 偏序了，可以扔掉，重复迭代这个弹栈过程即可，最后判一下 $i$ 是否会被栈顶全面偏序，如果不会就 push 进去。

总转移次数是 $O(n \log n)$ 的。

线段树分治优化

该优化也对四边形不等式适用。直接对于每个 $i$，将其能转移到的区间 $[L_i, R_i]$ 对应的 $\log$ 个线段树上的区间都插入一个 $i$。那么对于每个线段树上的区间，能转移到该区间的节点都在该区间外，所以我们就拥有了“反决策单调性”，即 $p$ 在这个区间对应的转移过程中单调递减。那么我们在线段树分治的内层直接对每个线段树表示的区间做前文提到的分治算法即可，整个过程是半在线的。

总转移次数是 $O(n \log^2 n)$ 的，该算法实质上是将离线算法套了一层分治变为半在线，并且可以处理转移区间任意的情况。