「DP 浅析」四边形不等式优化

下面的证明的思想多数为数学归纳、分类讨论或反证法。

简述

定义 $w(i,j)$ 为一个定义在 $\mathbb{Z}$ 上的二元函数，有如下定义：

定义 1：如果对于任意 ${\ell }_1\le {\ell }_2\le r_1\le r_2$，都有

$$w({\ell }_1,r_1)+w({\ell }_2,r_2)\le w({\ell }_1,r_2)+w({\ell }_2,r_1)$$

$w$ 满足四边形不等式（即“交叉小于包含”），如果等号始终成立，那么称 $w$ 满足四边形恒等式。

定义 2：如果对于任意 $\ell \le {\ell }^{\prime }\le r^{\prime }\le r$，都有 $w(\ell ,r)\ge w({\ell }^{\prime },r^{\prime })$ 成立，那么则称 $w$ 对于区间包含关系具有单调性。

定理 1：如果对于定义域上任意 $\ell <r$，都有

$$w(\ell ,r)+w(\ell +1,r+1)\le w(\ell ,r+1)+w(\ell +1,r)$$

成立，那么 $w(\ell ,r)$ 满足四边形不等式。

证明：先来证明对于任意 ${\ell }_1\le {\ell }_2\le r_1$，都有

$$\begin{array}{}\text{(1)}& w({\ell }_1,r_1)+w({\ell }_2,r_1+1)\le w({\ell }_1,r_1+1)+w({\ell }_2,r_1).\end{array}$$

对于 $i={\ell }_2-{\ell }_1$ 进行归纳，显然当 $i=0$ 时上式成立，下面证明对 $i\in [1,r_1-{\ell }_1]$ 成立。

首先根据归纳假设，

$$\begin{array}{}\text{(2)}& w({\ell }_1,r_1)+w({\ell }_1+i-1,r_1+1)\le w({\ell }_1,r_1+1)+w({\ell }_1+i-1,r_1),\end{array}$$

因为 $i\le r_1-{\ell }_1$，于是有 ${\ell }_1+i-1<r_1$，应当有

$$\begin{array}{}\text{(3)}& w({\ell }_1+i-1,r_1)+w({\ell }_1+i,r_1+1)\le w({\ell }_i+i,r_1)+w({\ell }_1+i-1,r_1+1),\end{array}$$

将 $(2)$ 与 $(3)$ 左右两边分别相加，于是有

$$w({\ell }_1,r_1)+w({\ell }_1+i,r_1+1)\le w({\ell }_1+1,r_1+1)+w({\ell }_1+i,r_1),$$

于是对于 $\mathrm{\forall }{\ell }_1,{\ell }_2,r_1\in \mathbb{Z},{\ell }_1\le {\ell }_2\le r_1$，$(1)$ 都成立。

在上面的基础上，我们再来证明对于 $\mathrm{\forall }{\ell }_1,{\ell }_2,r_1,r_2\in \mathbb{Z},{\ell }_1\le {\ell }_2\le r_1\le r_2$，都有四边形不等式成立。同理，对 $j=r_2-r_1$ 进行归纳，显然当 $j=0$ 时四边形不等式成立，下面对于 $j>0$ 的情况进行证明。

首先根据归纳假设，有

$$\begin{array}{}\text{(4)}& w({\ell }_1,r_1)+w({\ell }_2,r_1+j-1)\le w({\ell }_1,r_1+j-1)+w({\ell }_2,r_1),\end{array}$$

因为 $r_1+j-1\ge {\ell }_2\ge {\ell }_1$，根据 $(1)$，应当有

$$\begin{array}{}\text{(5)}& w({\ell }_1,r_1+j-1)+w({\ell }_2,r_1+j)\le w({\ell }_1,r_1+j)+w({\ell }_2,r_1+j-1)\end{array}$$

将 $(4)$ 与 $(5)$ 左右两边分别相加可得

$$w({\ell }_1,r_1)+w({\ell }_2,r_1+j)\le w({\ell }_1,r_1+j)+w({\ell }_2,r_1),$$

于是假设成立，即四边形不等式成立。

证毕.

应用

优化 2D1D 动态规划

区间型 DP

常见的一种动态规划的状态转移方程为

$$f_{\ell ,r}=\underset{\ell \le k<r}{min}\{f_{\ell ,k}+f_{k+1,r}\}+w(\ell ,r),(1\le \ell <r\le n)$$

直接简单实现上面的转移，那么时间复杂度为 $O(n^3)$，如果 $w(l,r)$ 满足一些特殊性质，那么我们可以用四边形不等式对其进行优化。

定理 2：如果 $w(\ell ,r)$ 满足四边形不等式且对于区间包含关系具有单调性，那么状态 $f_{l,r}$ 满足四边形不等式。

证明：定义 $g_{k,\ell ,r}=f_{\ell ,k}+f_{k+1,r}+w(\ell ,r)$，表示决策点为 $k$ 时的状态值，任取 ${\ell }_1\le {\ell }_2\le r_1\le r_2$，记 $u=\underset{{\ell }_1\le k<r_2}{\arg min}{g}_{k,{\ell }_1,r_2},v=\underset{{\ell }_2\le k<r_1}{\arg min}{g}_{k,{\ell }_2,r_1}$，分别表示 $f_{{\ell }_1,r_2}$ 和 $f_{{\ell }_2,r_1}$ 的最小最优决策点。

首先，如果 ${\ell }_1={\ell }_2$，那么显然成立，然后考虑对于 $r_2-r_1$ 进行归纳，显然当 $r_2-r_1=0$ 时成立。

• ${\ell }_1<{\ell }_2=r_1<r_2$ （$w$ 需要对于区间包含关系具有单调性）

  • 若 $u<r_1$，则 $f_{{\ell }_1,r_1}\le f_{{\ell }_1,u}+f_{u+1,r_1}+w({\ell }_1,r_1)$，根据归纳假设，有 $f_{u+1,r_1}+f_{{\ell }_2,r_2}\le f_{u+1,r_2}+f_{{\ell }_2,r_1}$，两式相加即得

    $$f_{{\ell }_1,r_1}+f_{{\ell }_2,r_2}\le f_{u+1,r_2}+f_{{\ell }_2,r_1}+f_{{\ell }_1,u}+w({\ell }_1,r_1)\le f_{{\ell }_2,r_1}+f_{{\ell }_1,r_2}$$

  • 若 $u\ge r_1$，则 $f_{{\ell }_2,r_2}\le f_{{\ell }_2,u}+f_{u+1,r_2}+w({\ell }_2,r_2)$，根据归纳假设，有 $f_{{\ell }_1,r_1}+f_{{\ell }_2,u}\le f_{{\ell }_1,u}+f_{{\ell }_2,r_1}$，两式相加即得

    $$f_{{\ell }_1,r_1}+f_{{\ell }_2,u}\le f_{{\ell }_1,u}+f_{{\ell }_2,r_1}+f_{u+1,r_2}+w({\ell }_2,r_2)\le f_{{\ell }_2,r_1}+f_{{\ell }_1,r_2}$$

• ${\ell }_1<{\ell }_2<r_1<r_2$（$w$ 仅需满足四边形不等式）

  • 若 $u\le v$，则 $l_1\le u<r_1,l_2\le v<r_2$，因此

    $$\begin{array}{rl}{f}_{l_1,r_1}\le g_{u,l_1,r_1}& =f_{l_1,u}+f_{u+1,r_1}+w(l_1,r_1)\\ f_{l_2,r_2}\le g_{v,l_2,r_2}& =f_{l_2,v}+f_{v+1,r_2}+w(l_2,r_2)\end{array}$$

    再由 $u+1\le v+1\le r_1\le r_2$ 和归纳假设知

    $$f_{u+1,r_1}+f_{v+1,r_2}\le f_{u+1,r_2}+f_{v+1,r_1}$$

    将前两个不等式累加，并将第三个不等式代入，可得

    $$\begin{array}{rl}{f}_{l_1,r_1}+f_{l_2,r_2}& \le f_{l_1,u}+f_{l_2,v}+f_{u+1,r_1}+f_{v+1,r_2}+w(l_1,r_1)+w(l_2,r_2)\\ & \le g_{u,l_1,r_2}+g_{v,l_2,r_1}=f_{l_1,r_2}+f_{l_2,r_1}\end{array}$$

  • 若 $v<u$，则 $l_1\le v<r_1,l_2\le u<r_2$，因此

    $$\begin{array}{rl}{f}_{l_1,r_1}\le g_{v,l_1,r_1}& =f_{l_1,v}+f_{v+1,r_1}+w(l_1,r_1)\\ f_{l_2,r_2}\le g_{u,l_2,r_2}& =f_{l_2,u}+f_{u+1,r_2}+w(l_2,r_2)\end{array}$$

    再由 $l_1\le l_2\le v\le u$ 和归纳假设知

    $$f_{l_1,v}+f_{l_2,u}\le f_{l_1,u}+f_{l_2,v}$$

    将前两个不等式累加，并将第三个不等式代入，可得

    $$\begin{array}{rl}{f}_{l_1,r_1}+f_{l_2,r_2}& \le f_{l_1,u}+f_{l_2,v}+f_{v+1,r_1}+f_{u+1,r_2}+w(l_1,r_2)+w(l_2,r_1)\\ & \le g_{u,l_1,r_2}+g_{v,l_2,r_1}=f_{l_1,r_2}+f_{l_2,r_1}\end{array}$$

综上所述，两种情形均有 $f_{l_1,r_1}+f_{l_2,r_2}\le f_{l_1,r_2}+f_{l_2,r_1}$，即四边形不等式成立。

证毕.

定理 3：若状态 $f$ 满足四边形不等式，记 $m_{l,r}=min\{k:f_{l,r}=g_{k,l,r}\}$ 表示最优决策点，则有

$$m_{l,r-1}\le m_{l,r}\le m_{l+1,r}(l+1<r)$$

证明：记 $u=m_{l,r},k_1=m_{l,r-1},k_2=m_{l+1,r}$，分情况讨论：

• 若 $k_1>u$，则 $u+1\le k_1+1\le r-1\le r$，因此根据四边形不等式有

  $$f_{u+1,r-1}+f_{k_1+1,r}\le f_{u+1,r}+f_{k_1+1,r-1}$$

  再根据 $u$ 是状态 $f_{l,r}$ 的最优决策点可知

  $$f_{l,u}+f_{u+1,r}\le f_{l,k_1}+f_{k_1+1,r}$$

  将以上两个不等式相加，得

  $$f_{l,u}+f_{u+1,r-1}\le f_{l,k_1}+f_{k_1+1,r-1}$$

  即 $g_{u,l,r-1}\le g_{k_1,l,r-1}$，但这与 $k_1$ 是最小的最优决策点矛盾，因此 $k_1\le u$。

• 若 $u>k_2$，则 $l\le l+1\le k_2\le u$，根据四边形不等式可得

  $$f_{l,k_2}+f_{l+1,u}\le f_{l,u}+f_{l+1,k_2}$$

  再根据 $k_2$ 是状态 $f_{l+1,r}$ 的最优决策点可知

  $$f_{l+1,k_2}+f_{k_2+1,r}\le f_{l+1,u}+f_{u+1,r}$$

  将以上两个不等式相加，得

  $$f_{l,k_2}+f_{k_2+1,r}\le f_{l,u}+f_{u+1,r}$$

  即 $g_{k_2,l,r}\le g_{u,l,r}$，但这与 $u$ 是最小的最优决策点矛盾，因此 $u\le k_2$。

证毕.

因此，如果在计算状态 $f_{l,r}$ 的同时将其最优决策点 $m_{l,r}$ 记录下来，那么我们对决策点 $k$ 的总枚举量将降为

$$\sum _{1\le l<r\le n}(m_{l+1,r}-m_{l,r-1})=\sum _{i=1}^n(m_{i,n}-m_{1,i})\le n^2$$

上式的第一个等号可以通过将两个 $\mathrm{\Sigma }$ 分别展开合并同类项得证。

另一形式

另一种常见的状态转移方程为

$$f_{i,j}=\underset{k\le j}{min}\{f_{i-1,k}+w(k,j)\},(1\le i\le n,1\le j\le m)$$

具有与上面同样的结论与性质。

优化 1D1D 动态规划

定理及证明

一种常见的状态转移方程为

$$f_i=\underset{0\le j<i}{min}\{f_j+w(i,j)\}$$

定理 4：若 $w$ 满足四边形不等式，那么 $f$ 具有决策单调性。

证明：设 $p_i$ 为 $f_i$ 的最优决策点，对于 $\mathrm{\forall }i\in [1,n],\mathrm{\forall }j\in [0,p_i-1]$，有

$$\begin{array}{}\text{(6)}& f_{p_i}+w(p_i,i)\le f_j+w(j,i),\end{array}$$

$\mathrm{\forall }{i}^{\prime }\in [i+1,n]$，由于 $w$ 满足四边形不等式，于是有

$$\begin{array}{}\text{(7)}& w(j,i)+w(p_i,i^{\prime })\le w(j,i^{\prime })+w(p_i,i),\end{array}$$

将 $(6)$ 和 $(7)$ 左右两部分分别相加即得

$$f_{p_i}+w(p_i,i^{\prime })\le f_j+w(j,i^{\prime }),$$

也就说明了应有 $p_{i^{\prime }}\ge p_i$，即决策单调性。

证毕.

实现

由于决策单调性，$p$ 一定是一个非严格递增的序列，我们对 $p$ 进行维护，即对于当前转移完的 $i$，我们考虑从哪里开始 $i$ 开始作为最优的决策点。

显然一种朴素的做法是直接在 $p$ 上进行二分，找到对应位置 $pos$，然后 $\mathrm{\forall }j\in [pos,n]$，将 $p_j$ 修改为 $i$。

一种更为简洁的做法是，用一个队列维护 $p$，利用 $p$ 是一个非严格递增的序列的性质，每一段相同的用一个三元组 $(t_k,l_k,r_k)$，表示当前 $\mathrm{\forall }i\in [l_k,r_k],p_i=t_k$.

同时，如果一个三元组的右边界已经小于当前处理的位置，它一定不再有贡献，可以直接丢掉，于是就类似与单调队列，此时第一个合法的队头就是该位置的最优决策点。

考虑用 $i$ 更新决策点的过程，我们按照以下步骤进行：

1. 取出队尾的三元组 $(t_k,l_k,r_k)$；
2. 若 $f_i+w(i,l_k)<f_{t_k}+w(t_k,l_k)$，令 $pos=l_k$，删掉该三元组，回到 1.
3. 若 $f_i+w(i,r_k)>f_{t_k}+w(t_k,r_k)$，直接到 5.
4. 在 $[l_k,r_k]$ 上二分，找到第一个可行位置，更新为 $pos$；
5. 在队尾加入 $(i,pos,n)$；

整体时间复杂度为 $O(n\log n)$.

参考资料

[1] 四边形不等式优化 - OI Wiki

[2] 四边形不等式 - Pedesis