四边形不等式概览.md

动态规划相关

通常需要排除一些不可能的决策点或者排序，以满足最优子结构或决策单调性。这通常在常数优化时被 oier 考虑到。

四边形不等式

• 区间包含单调性：如果对于任意 $l \leq l' \leq r' \leq r$ ，均有 $w(l',r') \leq w(l,r)$ 成立，则称函数 $w$ 关于区间包含关系具有单调性。
• 四边形不等式：如果对于任意 $l_1\leq l_2 \leq r_1 \leq r_2$ ，均有 $w(l_1,r_1)+w(l_2,r_2) \leq w(l_1,r_2) + w(l_2,r_1)$ 成立，则称函数 $w$ 满足四边形不等式（简记为“交叉小于包含”）。若等号永远成立，则称函数 $w$ 满足四边形恒等式 。

1D/1D的优化

我们常有方程 $$ f_{r} = \min_{l=1}^{r-1}{f_{l}+w(l,r)}\qquad\left(1 \leq r \leq n\right) $$ 定理 若函数 $w(l,r)$ 满足四边形不等式，则 $f$ 满足决策单调性，即：记 $h_{l,r}=f_l+w(l,r)$ 表示从 $l$ 转移过来的状态 $r$ , $k_{r}=\min{l:f_{r}=h_{l,r}}$ 表示最优决策点，有 $\forall r_1 \leq r_2:k_{r_1} \leq k_{r_2}$。

2D/1D的优化

区间类动态规划中，常常遇到形如下面的转移方程：

$$ f_{l,r} = \min_{k=l}^{r-1}{f_{l,k\pm 1,0}+f_{k\pm 1,0,r}} + w(l,r)\qquad\left(1 \leq l \leq r \leq n\right) $$ 对于不同的问题，$f_{i,j}$ 的边界取值可能不同。这对我们讨论的问题没有影响（源于华中师大一附中赵爽）。考试时请打表。

定理 若函数 $w(l, r)$ 满足四边形不等式（且满足区间包含单调性？），则 $f_{l,r}$ 也满足四边形不等式。（用数学归纳法证明）

定理 若 $f$ 满足四边形不等式，则 $f$ 满足决策单调性，即：记 $m_{l,r}=\min{k:f_{l,r} = g_{k,l,r}}$ 表示最优决策点，则有 $$m_{l,r-1} \leq m_{l,r} \leq m_{l+1,r}$$。

即若函数 $w(l, r)$ 满足四边形不等式，则 $f$ 满足决策单调性。只需枚举决策

k in c[i][j-1] to c[i+1][j]

核心代码

for(int bias=1; bias<n; bias++) // bias=j-i, where[i,j]
{
	for(int i=1,j; (j=i+k)<=n; i++)
	{
		f[i][j]=1e18;
		for(k=c[i][j-1]; k<=c[i+1][j]; k++)
           if(..<..) update f and c;
		f[i][j]+=x[j]-x[i-1];
	}
}

满足四边形不等式的函数类

摘自oi wiki。

为了更方便地证明一个函数满足四边形不等式，我们有以下几条性质：

性质 1. 若函数 $w_1(l,r),w_2(l,r)$ 均满足四边形不等式（或区间包含单调性），则对于任意 $c_1,c_2\geq 0$ ，函数 $c_1w_1+c_2w_2$ 也满足四边形不等式（或区间包含单调性）。

性质 2. 若存在函数 $f(x),g(x)$ 使得 $w(l,r) = f(r)-g(l)$ ，则函数 $w$ 满足四边形恒等式。当函数 $f,g$ 单调增加时，函数 $w$ 还满足区间包含单调性。

性质 3. 设 $h(x)$ 是一个凸函数，若函数 $w(l,r)$ 满足四边形恒等式并且对区间包含关系具有单调性，则复合函数 $h(w(l,r))$ 也满足四边形不等式。

性质 4. 设 $h(x)$ 是一个单调增加的凸函数，若函数 $w(l,r)$ 满足四边形不等式并且对区间包含关系具有单调性，则复合函数 $h(w(l,r))$ 也满足四边形不等式和区间包含单调性。

凸函数（Convex Function）的定义在国内教材中有分歧，本文指（可微的）下凸函数，即一阶导数单调增加的函数。

更高更妙的记忆与性质

若两函数 $w_{1,2}(l,r)$ 均满足四边形不等式（或区间包含单调性），则其（正系数）线性组合也满足四边形不等式（或区间包含单调性）。

若存在函数 $f(x),g(x)$ 使得 $w(l,r) = f(r)-g(l)$ ，则 $w$ 满足四边形恒等式。当函数 $f,g$ 单调增加时，函数 $w$ 还满足区间包含单调性。

设 $h(x)$ 是一个凸函数，若函数 $w(l,r)$ 满足四边形恒等式并且对区间包含关系具有单调性，则其复合函数 $h(w(l,r))$ 也满足四边形不等式。若 $h(x)$ 还单调增加，复合函数 $h(w(l,r))$ 也满足区间包含单调性。