四边形不等式条件

任意 $a1\leq a2<b1\leq b2$,有 $F(a_1,b_1)+F(a_2,b_2)\leq F(a_1,b_2)+F(a_2,b_1)$ 则函数 F 满足四边形不等式

基本概念

区间包含的单调性：如果对于 $i≤i’<j≤j’$，有 $w(i’,j)≤w(i,j’)$，那么说明 w 具有区间包含的单调性。（小区间的值不超过大区间的值）

定理一：如果上述的 w 函数同时满足区间包含单调性和四边形不等式性质，那么函数 m 也满足四边形不等式性质

定义 s(i,j)表示 m(i,j)取得最优值时对应的下标（即 $i≤k≤j$ 时，k 处的 w 值最大，则 $s(i,j)=k$)

定理二：假如 m(i,j)满足四边形不等式，那么 s(i,j)单调，即 $s(i,j)≤s(i,j+1)≤s(i+1,j+1)$

优化

若 F 满足 F[i,j] = opt{F[i,k]+F[k,j] + w(i,j)} (i<=k<=j) 时间复杂度为 O(N^3)

如果 w 函数满足区间包含单调性和四边形不等式性质,则原来的状态转移方程可以改写为下式： $$F(i,j)=min{F(i,k-1),F(k,j)}+w(i,j)(s(i,j-1)≤k≤s(i+1,j))$$