四边形不等式

· · 算法·理论

【定义】

四边形不等式是对一个二元函数 w(l,r) 定义的。这个 w(l,r) 可以看作一段区间的 "代价"。

如果 \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() 满足四边形不等式。 简记为 "交叉小于包含"。

同时有一个等价结论：w() 满足四边形不等式 \iff w(l,r-1)+w(l+1,r)\le w(l,r)+w(l+1,r-1)。

小结论：两个函数满足四边形不等式，它们的和也满足四边形不等式。

单调性：如果函数 w 对 \forall l_1\le l_2\le r_1\le r_2 都有 w(l_2,r_1)\le w(l_1,r_2)，称 w 有单调性。

【三个模型】

四边形不等式的优化基于最早的最优决策点的位置变化。记 opt(l,r) 为 f_{l,r} 的最早的最优决策点。

【合并模型】

f_{l,r}=\min_{l\le k<r}\{f_{l,k}+f_{k+1,r}\}+w(l,r)

条件：w 满足四边形不等式且满足单调性。

结论：f 满足四边形不等式；opt(i,j)\le opt(i,j+1)\le opt(i+1,j+1)（双单调性）。

有了这个结论，可以按照 r-l+1 的大小枚举，因为 opt(l,r-1)\le opt(l,r)\le opt(l+1,r)，而 opt(l,r-1),opt(l+1,r) 已经求出来了，所以可以直接枚举 [opt(l,r-1),opt(l+1,r)] 中的每个数作为决策位置求最优。

对于 r-l+1 固定的情况下，可以发现 [opt(l,r-1),opt(l+1,r)] 恰好首尾相连拼出来一个 O(n) 的区间。所以总复杂度 O(n^2)。

【分组模型】

f_{i,k}=\min_{0\le j<i}\{f_{j,k}+w(j,i)\}

有的可能是 +w(j+1,i) 不过不影响。

条件：w 满足四边形不等式且满足单调性。

结论：opt(i,j-1)\le opt(i,j)\le opt(i+1,j)。

可以类似上面合并模型得到 O(n^2) 的方法。

这里有另外一种方法：二分队列。用一个队列维护若干个区间，每个区间都是一段极大的决策点。每加入一个新决策点，从后往前检查每个旧决策点，看新决策点是不是更优；如果是一部分优，一部分不优，就二分找到分割点，改一下。复杂度 O(n\log n)

还有另外一种方法：分治。假如当前求 f[l\sim r][k]，备选决策区间为 [ql,qr]。把 [ql,qr] 扫一遍，找到 f[mid][k] 的最优决策点 p。则 f[l\sim mid - 1][k] 的决策区间为 [ql,p]，另一边同理。每一层 O(n)，递归层数 O(\log n)，所以求 f[][k] 的复杂度 O(n\log n)。总复杂度 O(nk\log n)。

【1d1d 模型】

f_i=\min_{0\le j<i}\{f_j+w(j,i)\}

条件：w 满足四边形不等式。

结论：opt(i)\le opt(i+1)。

做法类似上面。