学习笔记 - 四边形不等式的理论证明

老师讲课就让背结论……不管,还是要知道四边形不等式为什么正确!

参考 OI wiki


# 区间DP的四边形不等式

对于区间 $(l,r)$,它的DP值为 $f(l,r)$,代价为 $c(l,r)$。
有转移式 $f(l,r)=f(l,k)+f(k+1,r)+c(l,r)$。

如果对于任意 $l_1\leq l_2\leq r_1\leq r_2$ 都有:

  • 区间包含的单调性:$c(l_2,r_1)\leq c(l_1,r_2)$;(因为区间 $(l_2,r_1)\subseteq (l_1,r_2)$)
  • “交叉小于包含”:$c(l_1,r_1)+c(l_2,r_2)\leq c(l_1,r_2)+c(l_2,r_1)$;

那么存在四边形不等式:$f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,r_2)+f(l_2,r_1)$。

- 证明

首先假设四边形不等式成立:

令 $l_1\leq l_2\leq r_1\leq r_2$,且满足:

  1. $c(l_2,r_1)\leq c(l_1,r_2)$;
  2. $c(l_1,r_1)+c(l_2,r_2)\leq c(l_1,r_2)+c(l_2,r_1)$;
  3. $f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,r_2)+f(l_2,r_1)$。

设 $u,v$ 分别表示 $f(l_1,r_2),f(l_2,r_1)$ 的最优决策点

  1. 若 $u\leq v$,则 $l_1\leq u\leq v<r_1\leq r_2$;所以 $u+1\leq v+1\leq r_1\leq r_2$。

    > Hint

    $u,v$ 是 $f(l_1,r_2),f(l_2,r_1)$ 的最优决策点,但不一定是 $f(l_1,r_1),f(l_2,r_2)$ 的最优决策点。因此是 “$\leq$”

    由 (1)+(2) :$f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,u)+f(u+1,r_1)+c(l_1,r_1)+f(l_2,v)+f(v+1,r_2)+c(l_2,r_2)$
    代入 (3) :$f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,u)+f(u+1,r_2)+c(l_1,r_1)+f(l_1,v)+f(v+1,r_1)+c(l_2,r_2)$

    因为 $c(l_1,r_1)+c(l_2,r_2)\leq c(l_1,r_2)+c(l_2,r_1)$;
    所以 $f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,u)+f(u+1,r_2)+c(l_1,r_2)+f(l_1,v)+f(v+1,r_1)+c(l_2,r_1)$

    因为 $u,v$ 分别是 $f(l_1,r_2),f(l_2,r_1)$ 的最优决策点;

    代入可得 $f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,r_2)+f(l_2,r_1)$;

    得证。

  2. 若 $v<u$,则 $l_1\leq l_2\leq v<u\leq r_2$;

    因为 $l_1\leq l_2\leq v<u$;
    所以 $f(l_1,v)+f(l_2,u)\leq f(l_1,u)+f(l_2,v) (6)$;

    由 (4)+(5):$f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,v)+f(v+1,r_1)+c(l_1,r_1)+f(l_2,u)+f(u+1,r_2)+c(l_2,r_2)$
    代入 (6):$f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,u)+f(u+1,r_2)+f(l_2,v)+f(v+1,r_1)+c(l_1,r_1)+c(l_2,r_2)$

    因为 $c(l_1,r_1)+c(l_2,r_2)\leq c(l_1,r_2)+c(l_2,r_1)$
    所以 $f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,u)+f(u+1,r_2)+f(l_2,v)+f(v+1,r_1)+c(l_1,r_2)+c(l_2,r_1)$

    也就是 $f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,r_2)+f(l_2,r_1)$;

    得证。

- 决策单调性

对于DP状态 f[l][r] 表示区间 $[l,r]$ 的总代价,若转移式如下面形式:f[l][r]=min/max{f[l][k]+f[k+1][r]+cst(l,r)},且 cst(l,r) 满足四边形不等式。

根据之前的证明,可知 f[l][r] 也满足四边形不等式。还有一个结论——记 t[l][r] 表示 f[l][r]所有最优决策点中最小的一个,则有 t[l][r-1]<=t[l][r]<=t[l+1][r]

不妨设 f[l][r] 取 min(取 max 一样的),证明如下:

a=f[l][r-1],b=f[l][r],c=f[l+1][r]($l\le a<r-1,l\le b<r,l+1\le c<r$)

则需证明 $a\le b\le c$,考虑反证法

  1. 假设 $a>b$:

    则 $b+1\le a+1\le r-1< r$,根据“交叉小于包含”:

    又因为 $b$ 是 f[l][r] 的最优决策点:

    两式相加可得:

    也就是说 f[l][r-1] 通过 b 来转移不会比 a 差,与 a 是最小的最优决策点矛盾。

  2. 假设 $b>c$:

    那么 $l<l+1<c\le b$,根据“交叉小于包含”:

    又因为 $c$ 是 f[l+1][r] 的最优决策点:

    两式相加可得:

    也就是说 f[l][r] 通过 c 来转移不会比 b 差,与 b 是 f[l][r] 的最小的最优决策点矛盾。

于是得证。


# 阶段性DP的决策单调性

对于一类DP:f[i][j] 表示第 j 个阶段、状态 i 的最优值。

比如“把n个数分为连续的m段,求每一段异或之和的最小值”,定义 f[i][j] 表示“前 i 个数分了 j 段”,换句话说就是“在 ‘分了 j 段’ 这个阶段下,状态为 ‘前 i 个数’ 的最小值”。

from SPOJ - Ada and Mold

为什么叫“阶段性”?观察其转移式,可以找到如下模型:

1
f[i][j]=min/max{f[k][j-1]+w(k+1,i)}

因此 f[][j] 只与 f[][j-1] 有关,即只与上一个阶段有关。

- 结论

定义 p(i,j)f[i][j] 的最小的最优转移点。

w(l,r) 满足四边形不等式,则 $p(i,j-1)\le p(i,j)\le p(i+1,j)$,因此可以用类似区间DP的方法优化。

- 证明

设 $a,b,c$ 分别为 $p(i,j-1),p(i,j),p(i+1,j)$。仍然考虑反证:

  1. 假设 $b<a$,则 $b<a\le j-1<j$:

    根据 $w(l,r)$ 的四边形不等式:

    两式相加:

    于是得到如果 f[i][j-1] 通过 b 转移会比 a 转移优……然后就推出矛盾了。于是 $a\le b$。

  2. 假设 $c<b$,则 $c<b\le j\le j+1$:

    根据 $w(l,r)$ 的四边形不等式:

    两式相加:

    也就是说 f[i][j+1] 用 c 转移会比用 b 优。但是根据之前证明的 “$a\le b$”:$p(i,j)\le p(i,j+1)$

    推出矛盾,所以 $b\le c$
    

得证。


The End

Thanks for reading!

这篇博客是 2019.12.8 开始写的……咕了好久了

0%