四边形不等式优化

动态规划相关

通常需要排除一些不可能的决策点或者排序，以满足最优子结构。这通常在常数优化时被 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];
    }
}