四边形不等式优化
应用于类似以下dp转移方程。
f
i
=
min
1
≤
j
≤
i
(
w
i
,
j
,
f
i
)
f_{i}=\min_{1\le j\le i}(w_{i,j},f_{i})
fi=1≤j≤imin(wi,j,fi)
假设
w
i
,
j
w_{i,j}
wi,j 可以在
O
(
1
)
O(1)
O(1) 的时间内进行计算。
在正常情况下，此状态转移方程的时间复杂度是 O ( n 2 ) O(n^2) O(n2)。
对于问题 i i i，我们需要考虑所有的有关决策 j j j，但是当其满足决策单调性时，就可以缩小决策空间，减少时间复杂度。
四边形不等式：
约定：
对于类似
a
≤
b
≤
c
≤
d
a\le b\le c\le d
a≤b≤c≤d 都成立，若二元函数
w
i
,
j
w_{i,j}
wi,j 满足以下条件
w
a
,
c
+
w
b
,
d
≤
w
a
,
d
+
w
b
,
c
w_{a,c}+w_{b,d}\le w_{a,d}+w_{b,c}
wa,c+wb,d≤wa,d+wb,c
则称
w
i
,
j
w_{i,j}
wi,j 满足四边形不等式。
特别的，若等号永远成立，则称 w i , j w_{i,j} wi,j 为四边形恒等式。
重点：因为四边形不等式是用来优化时间复杂度的，所以四边形不等式给出了一个决策单调性的充分不必要条件。
利用决策单调性，可以使用二分查找，使其查询时间复杂度降低为 O ( N log N ) O(N \log N) O(NlogN)。
区间包含单调性
若 w b , c ≤ w a , d w_{b,c}\le w_{a,d} wb,c≤wa,d，则称 w w w 满足区间包含单调性。
- 既包含，又满足决策单调性。
- 满足四边形不等式的形象化图片。
方程：
$$
w_{l,r+1}-w_{l,r}=a_{r+1}-a_{\lfloor\frac{l+r+1}{2}\rfloor}
\
w_{l+1,r+1}-w_{l+1,r}=a_{r+1}-a_{\lfloor\frac{l+r+2}{2}\rfloor}
\
$$
