「四边形不等式优化」学习笔记

博主学术不精，若有错误恳请指出QwQ

定义

区间包含单调性 ：如果 $ forall l le l' le r' le r $ ，都有 (w(l',r')le w(l,r)) ，那么称函数 (w) 对于区间包含关系具有单调性。

四边形不等式 ：如果 $ forall l_1 le l_2 le r_1 le r_2 $ ，都有 (w(l_1,r_1) + w(l_2,r_2) le w(l_1,r_2) + w(l_2,r_1)) ，那么称函数 (w) 满足四边形不等式，（等号永远取等则成为四边形恒等式）。

区间DP（2D1D）

转移式形如：

[large f_{l,r}= min_{k=l}^{k<r} left( f_{l,k} + f_{k+1,r} ight) + w(l,r) ]

一些定理

引理1 ：如果 (w(l,r)) 满足区间包含单调性且四边形不等式，那么 (f_{l,r}) 也满足四边形不等式。

证明：

对 (r_2 - l_1) 的长度使用归纳法， (l_1 = l_2) 或 (r_1 = r_2) 时显然成立。

设 (u) 为 (f_{l_1,r_2}) 的最小最优决策点， (v) 为 (f_{l_2,r_1}) 的最小最优决策点。

发现当 (l_2=r_1) 时 (v) 是没有意义的，所以提出来特别考虑。

如果 (l_1 < l_2 = r_1 < r_2) ，那么

如果 (u < r_1) ，则

[large f_{l_1,r_1} le f_{l_1,u} + f_{u+1,r_1} + w(l_1,r_1)\ large ext{又由归纳假设 } f_{u+1,r_1} + f_{l_2,r_2} le f_{u+1,r_2} + f_{l_2,r_1} \ large ext{且 } w(l_1,r_1) le w(l_1,r_2) \ large ext{所以有 } f_{l_1,r_1} + f_{l_2,r_2} le f_{l_2,r_1} + f_{l_1,u} + f_{u+1,r_2} + w(l_1,r_2)\ large = f_{l_2,r_1} + f_{l_1,r_2} ]

如果 (r_1 le u) ，同理。

如果 (l_1 < l_2 < r_1 < r_2) ，就不需要用到「区间包含单调性」这一条件了，证明类似。

定理1 ：如果 (f_{l,r}) 满足四边形不等式，设 (g_{l,r}) 为 (f_{l,r}) 的最小最优决策点，那么有

[large g_{l,r-1} le g_{l,r} le g_{l+1,r} (l+1<r) ]

设 (k_1 = g_{l,r-1}) ， (k_2 = g_{l+1,r}) ，(u=g_{l,r}) ，

以下进行分讨，如果 (u < k_1) ，则有 (u + 1 le k_1 + 1 le r-1 le r) 。
所以：

[large f_{u+1,r-1} + f_{k_1 + 1,r} le f_{u+1,r} + f_{k_1+1,r-1}\ large ext{又有， } f_{l,u} + f_{u+1,r} le f_{l,k_1} + f_{k_1 + 1 , r}\ large ext{相加得：} f_{l,u} + f_{u+1,r-1} le f_{l,k_1} + f{k_1+1,r-1}\ ]

这说明 (u) 比 (k_1+1) 对 (f_{l,r-1}) 的贡献更优，与题设矛盾。

(k_2<u) 的情况类似，故不再赘述。

另一形式的区间 DP

[large f_{i,j} = min_{k=1}^{j-1} left{ f_{i-1,k} + w(j,k) ight} ]

有

[large g_{i,j-1} le g_{i,j} le g_{i+1,j} ]

到此，区间 DP 的四边形不等式优化已经讲解完毕，以下其他形式的四边形不等式优化也十分类似，不再书写证明。

1D1D 动态规划

形如 (f_i = min_{j=1}^{i-1}left{ f_{j} + w(i,j) ight}) 。

实际上跟前一个式子长得几乎一模一样，区别在于前者固定了层数，而这个没有。

定理

这个形式就比较简单了。

[large g_{i-1} le g_{i} ]

然而我们发现，后两个优化都需要前后的 (g) 来限定范围，没有一定优先的 DP 顺序，而第一个优化可以以长度为优先级进行 DP 。
第一个优化可以令所有点在同一层中被遍历的次数是 (O(n)) 的，总复杂度被优化至 (O(n^2))。

对于后两个优化，我们尽量让每个点在进行 DP 的时候有上下界以避免不必要的计算，首先肯定可以想到分治，每层会将当前的决策区间期望减半，于是总复杂度就是 (O(n log n)) 的。