0x5B 四边形不等式

设 $w(x, y)$ 是定义在整数集合上的二元函数。若对于定义域上的任意整数 $a, b, c, d$ ，其中 $a \leq b \leq c \leq d$ ，都有 $w(a, d) + w(b, c) \geq w(a, c) + w(b, d)$ 成立，则称函数 $w$ 满足四边形不等式。

定理（四边形不等式的另一种定义）

设 $w(x, y)$ 是定义在整数集合上的二元函数。若对于定义域上的任意整数 $a, b$ ，其中 $a < b$ ，都有 $w(a, b + 1) + w(a + 1, b) \geq w(a, b) + w(a + 1, b + 1)$ 成立，则函数 $w$ 满足四边形不等式。

证明：

对于 $a < c$ ，有 $w(a, c + 1) + w(a + 1, c) \geq w(a, c) + w(a + 1, c + 1)$ 。

对于 $a + 1 < c$ ，有 $w(a + 1, c + 1) + w(a + 2, c) \geq w(a + 1, c) + w(a + 2, c + 1)$ 。

两式相加，得到 $w(a,c + 1) + w(a + 2,c)\geq w(a,c) + w(a + 2,c + 1)$

依此类推，对任意的 $a \leq b \leq c$ ，有 $w(a, c + 1) + w(b, c) \geq w(a, c) + w(b, c + 1)$ 。

同理，对任意的 $a \leq b \leq c \leq d$ ，有 $w(a, d) + w(b, c) \geq w(a, c) + w(b, d)$ 。

$\spadesuit$ 一维线性DP的四边形不等式优化

对于形如 $F[i] = \min_{0 \leq j < i} \{F[j] + val(j, i)\}$ 的状态转移方程，记 $p[i]$ 为令 $F[i]$ 取到最小值的 $j$ 的值，即 $p[i]$ 是 $F[i]$ 的最优决策。若 $p$ 在 $[1, N]$ 上单调不减（非严格单调递增），则称 $F$ 具有决策单调性。

定理（决策单调性）

在状态转移方程 $F[i] = \min_{0 \leq j < i} \{F[j] + val(j, i)\}$ 中，若函数 $val$ 满足四边形不等式，则 $F$ 具有决策单调性。

证明：

$\forall i \in [1, N]$ , $\forall j \in [0, p[i] - 1]$ , 根据 $p[i]$ 的最优性, 有:

$\forall i^{\prime}\in [i + 1,N]$ ，因为val满足四边形不等式，有：

移项得：

与第一个等式相加，有：

这个不等式的含义为，以 $p[i]$ 作为 $F[i']$ 的决策，比以 $j < p[i]$ 作为 $F[i']$ 的决策更优。换言之， $F[i']$ 的最优决策不可能小于 $p[i]$ ，即 $p[i'] \geq p[i]$ 。所以 $F$ 有决策单调性。

证毕。

当 $F$ 有决策单调性时，我们可以把 $F[i] = \min_{0\leq j < i}\{F[j] + val(j,i)\}$ 的计算时间从 $O(N^2)$ 优化到 $O(N\log N)$ 。

考虑对 $p$ 数组进行维护。最初 $p$ 数组全部为 0。在 $i$ 循环进行的任意时刻，根据 $p[i]$ 的单调性， $p$ 的情况如下图所示：

当求出一个新的 $F[i]$ 时，我们应该考虑 $i$ 可以作为哪些 $F[i']$ $(i' > i)$ 的最优决策。根据决策单调性，最终我们会找到一个位置，在该位置之前， $p$ 数组目前存储的决策都比 $i$ 好，在该位置之后， $p$ 数组目前存储的决策都比 $i$ 差。我们要做的就是快速找到上述位置，在 $p$ 数组中把该位置之后的部分都变为 $i$ ：

直接修改一个数组效率当然很低。事实上，我们可以建立一个队列，代替 $p$ 数组。队列中保存若干个三元组 $(j, l, r)$ ， $j$ 表示决策， $l, r$ 表示目前 $p[l \sim r]$ 的值都是 $j$ 。

例如，第一幅图就可以用5个三元组 $(j_{1},1,2),(j_{2},3,3),(j_{3},4,6),(j_{4},7,8),(j_{5},9,11)$ 来表示。我们从队尾开始检查，判断出整个 $(j_{4},7,8),(j_{5},9,11)$ 都不如 $i$ 优，直接从队尾删除。而 $(j_{3},4,6)$ 左端比 $i$ 优，右端比 $i$ 差。因此，我们在 $(j_{3},4,6)$ 里二分查找，

即可确定所求的位置。最后我们把 $(j_{3},4,6)$ 变为 $(j_{3},4,5)$ ，把 $(i,6,11)$ 入队，即可得到上页第二幅图所示的情景。

另外，队列中没有必要保存小于 $p[1 \sim i - 1]$ 的部分，我们可以通过检查队头来排除掉过时的决策。这样就可以像许多单调队列问题一样，直接取队头为最优决策了。

总而言之，对于每个 $i \in [1, N]$ ，我们执行以下操作：

1. 检查队头：设队头为 $(j_0, l_0, r_0)$ ，若 $r_0 = i - 1$ ，删除队头。否则令 $l_0 = i$ 。

2. 取队头保存的 $j$ 为最优决策，执行状态转移，计算出 $F[i]$ 。
   3.尝试插入新决策 $i$ ，步骤如下：

(1)取出队尾，记为 $(j_{t},l_{t},r_{t})$
(2) 若对于 $F[l_{t}]$ 来说， $i$ 是比 $j_{t}$ 更优的决策，即 $F[i] + \text{val}(i, l_{t}) \leq F[j_{t}] + \text{val}(j_{t}, l_{t})$ ，记 $pos = l_{t}$ ，删除队尾，回到步骤(1)。
(3) 若对于 $F[r_{t}]$ 来说， $j_{t}$ 是比 $i$ 更优的决策，即 $F[j_{t}] + \text{val}(j_{t}, r_{t}) \leq F[i] + \text{val}(i, r_{t})$ ，去往步骤(5)。
(4) 否则，在 $[l_t, r_t]$ 上二分查找，求出位置 $pos$ ，在此之前决策 $j_t$ 更优，在此之后决策 $i$ 更优，去往步骤(5)。
(5) 把三元组 $(i, pos, N)$ 插入队尾。

请读者结合以下例题尝试实现上述过程。

*【例题】诗人小 G NOI2009/BZOJ1563

小G是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。

一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小G对于排版中的每行定义了一个不协调度，为这行的实际长度与行标准长度差值绝对值的 $P$ 次方，而一个排版的不协调度为所有行不协调度的总和。

小G最近又作了几首诗，现在请你对这几首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。

诗中的句子数 $N$ 不超过 $10^{5}$ , 每句的字符数不超过 30, 行标准长度 $L$ 不超过 $3 * 10^{6}$ , $P$ 不超过 10。

设 $F[i]$ 表示对前 $i$ 句诗排版的最小不协调度，记 $a[i]$ 为第 $i$ 句诗的长度，

sum[i] 为前 $i$ 句诗的总长度。

这里 $val(j,i) = |(sum[i] - sum[j]) + (i - j - 1) - L|^P$ ，存在大量 $i,j$ 的高次乘积项，不适合用单调队列或斜率优化。于是，我们尝试判断 $val(j,i)$ 是否满足四边形不等式。

要证明对于任意 $j < i$ ， $\operatorname{val}(j,i + 1) + \operatorname{val}(j + 1,i)\geq \operatorname{val}(j,i) + \operatorname{val}(j + 1,i + 1)$ 只需证明 $\operatorname{val}(j + 1,i) - \operatorname{val}(j + 1,i + 1)\geq \operatorname{val}(j,i) - \operatorname{val}(j,i + 1)$ 。

记 $u = (sum[i] + i) - (sum[j] + j) - (L + 1)$ 。

记 $v = (sum[i] + i) - (sum[j + 1] + j + 1) - (L + 1)$ 。

只需证明 $|v|^p - |v + (a[i + 1] + 1)|^p \geq |u|^p - |u + (a[i + 1] + 1)|^p$ 。

显然 $u > v$ 。故只需证明对任意常数 $c$ ，函数 $y = |x|^P - |x + c|^P$ 单调递减。

当 $P$ 为奇数且 $x \in [-c,0]$ 时，函数写作 $y = -x^{P} - (x + c)^{P}$ 。对 $x$ 求导，得到 $y' = -P * x^{P-1} - P * (x + c)^{P-1}$ ，因为 $P-1$ 是偶数， $P$ 是正整数，所以 $y' \leq 0$ 。从而 $y$ 关于 $x$ 单调递减。对于 $P$ 为偶数、 $x \in [-\infty, -c]$ 或 $x \in [0, +\infty]$ 的情况，利用导数，同理可证。

综上所述， $val(j, i)$ 满足四边形不等式。因此， $F$ 满足决策单调性。按照我们之前讲解的方法，用队列维护决策三元组，即可在 $O(N \log N)$ 的时间内解决本题。

$\spadesuit$ 二维区间DP的四边形不等式优化

在区间DP问题，例如“石子合并”一题中，我们经常遇到下面这样的状态转移方程：

利用四边形不等式，也可以对该方程的状态转移进行优化。

定理

在状态转移方程 $F[i,j] = \min_{i\leq k < j}\{F[i,k] + F[k + 1,j] + w(i,j)\}$ 中（特别地， $F[i,i] = w(i,i) = 0$ ，如果下面两个条件成立：

1. $w$ 满足四边形不等式。

2. 对于任意的 $a \leq b \leq c \leq d$ ，有 $w(a, d) \geq w(b, c)$ 。

那么 $F$ 也满足四边形不等式。

证明：

当 $i + 1 = j$ 时， $F[i,j + 1] + F[i + 1,j] = F[i,i + 2] + F[i + 1,i + 1] = F[i,i + 2]$ 。

若 $F[i,i + 2]$ 的最优决策是 $i + 1$ ，则 $F[i,i + 2] = F[i,i + 1] + F[i + 1,i + 2] + w(i,i + 2)\geq F[i,i + 1] + F[i + 1,i + 2] = F[i,j] + F[i + 1,j + 1]$ 。

若 $F[i,i + 2]$ 的最优决策是 $i$ ，则 $F[i,i + 2] = F[i,i] + F[i + 1,i + 2] + w(i,i + 2) = w(i + 1,i + 2) + w(i,i + 2)\geq w(i + 1,i + 2) + w(i,i + 1) = F[i + 1,i + 2] + F[i,i + 1].$

故当 $j - i = 1$ 时，四边形不等式对 $F(i,j)$ 成立。

接下来，用数学归纳法，假设当 $j - i < k$ 时，四边形不等式对 $F(i,j)$ 成立。考虑 $j - i = k$ 的情况。设 $F[i,j + 1]$ 以 $x$ 为最优决策， $F[i + 1,j]$ 以 $y$ 为最优决策。不妨设 $i + 1 \leq x \leq y$ 。

根据 $x$ 和 $y$ 的最优性，有：

对于 $F[i,j]$ 和 $F[i + 1,j + 1]$ ， $x$ 和 $y$ 是任意决策（不一定最优），故：

因为 $w$ 满足四边形不等式，所以：

根据归纳假设，有：

结合这两个不等式，比较①②两式，得到：

证毕。

定理（二维决策单调性）

在状态转移方程 $F[i,j] = \min_{i\leq k < j}\{F[i,k] + F[k + 1,j] + w(i,j)\}$ 中（特别地， $F[i,i] = w(i,i) = 0$ ），记 $P[i,j]$ 为令 $F[i,j]$ 取到最小值的 $k$ 值。

如果 $F$ 满足四边形不等式，那么对于任意 $i < j$ ，有 $P[i,j - 1] \leq P[i,j] \leq P[i + 1,j]$ 。

证明：

为方便起见，记 $p = P[i,j]$ ，对于任意的 $i < k\leq p$ ，因为 $F$ 满足四边形不等式：

移项可得：

根据 $p$ 的最优性，有：

因此：

这意味着对于 $F[i + 1,j]$ ， $\mathcal{P}$ 比任意的 $k\leq p$ 更优。因此 $P[i + 1,j]\geq P[i,j]$ 。

类似地，同理可证 $P[i,j - 1]\leq P[i,j]$

证毕。

【例题】再探石子合并

题意与 $0 \times 53$ 节的“石子合并”相同，数据范围 $N \leq 5000$ 。

石子合并问题的DP状态转移方程为：

$\sum_{i = l}^{r}A_{i}$ 是区间和，显然满足四边形不等式，且取到等号。

根据上面两条定理，我们只需要在 $P[l,r - 1]\leq k\leq P[l + 1,r]$ 的范围内对 $\pmb{k}$ 进行枚举，求出 $F[l,r]$ 和 $P[l,r]$ 。算法的时间复杂度为： $\mathrm{O}\bigl (\sum_{l = 1}^{N - 1}\sum_{r = l + 1}^{N}(P[l + 1,r] -$ $P[l,r - 1] + 1)\big) = O\bigl (\sum_{l = 1}^{N - 1}(P[l + 1,N] - P[1,N - l] + N - l)\bigr) = O(N^2)\circ$

事实上，石子合并问题还有 $O(N \log N)$ 复杂度的非动态规划算法，感兴趣的读者可以自行查阅相关资料，并完成题目 POJ1738。

到此为止，我们对动态规划优化策略的探讨就告一段落。请读者再次回顾 $0 \times 56 \sim 0 \times 58$ 节的各个模型和例题，理解每一种优化的本质，尝试作出一份总结，做到对何种情况下适合使用何种优化方法有初步的认识。