决策单调性优化

标签：le 定义 不等式 决策 ge 四边形 优化 单调

数学推导比较多。但是充斥着对称美。

单调队列/斜率优化，都是决策单调性优化。这篇主要说四边形不等式优化。

还没写完。

---

基本定义

四边形不等式：对于二元函数 \(w_{x,y}\)，如果对于定义域内任意 \(a\le b\le c\le d\)，都有 \(w_{a,b} + w_{c,d} \ge w_{a, c} + w_{b, d}\)（相交 \(\le\) 包含），那么称 \(w_{i,j}\) 满足四边形不等式。 （定义①）

等价转化

对于二元函数 \(w_{x,y}\)，若对于任意 \(a<b\)，存在 \(w_{a,b+1} + w_{a+1,b} \ge w_{a,b} + w_{a+1,b+1}\)，那么 \(w_{i,j}\) 也满足四边形不等式。（定义②）

定义①通常用来推出某些结论，定义②通常用来证明某个二元函数满足四边形不等式。

证明等价：
对于 \(c > a\)，如果 \(c = a + 1\)，则有：\(w_{a,c+1} + w_{a+1,c} \ge w_{a,c} + w_{a+1,c+1}\) 成立，否则有：

\[w_{a,c+1} + w_{a+1,c} \ge w_{a,c} + w_{a+1,c+1} \\ w_{a+1,c+1} + w_{a+2,c} \ge w_{a+1,c} + w_{a+2,c+1} \]

加起来得到：

\[w_{a,c+1} + w_{a+2,c} \ge w_{a,c} + w_{a+2,c+1} \]

以此类推，得到对于任意 \(a\le b\le c\)，有：

\[w_{a,c+1} + w_{b,c} \ge w_{a,c} + w_{b,c+1} \]

故技重施。对于 \(c < maxn\)，

\[w_{a,c+2} + w_{b,c+1} \ge w_{a,c+1} + w_{b,c+2} \]

加起来得到：

\[w_{a,c+2} + w_{b,c} \ge w_{a,c} + w_{b,c+2} \]

以此类推，得到定义①。

标签：le,定义,不等式,决策,ge,四边形,优化,单调
From： https://www.cnblogs.com/Zeardoe/p/16974725.html