1. 四边形不等式
1.1 小标题该怎么起阿
考虑一个形式如下的 DP:
\[f_{i} = \min_{j = 1}^{i}val(j, i) \]其中 \(i\) 满足 \(1 \leq i \leq n\)。
设 \(f_{i}\) 的最优决策点为 \(oper_{i}\)。
1.2 一些概念
决策单调性:指满足 \(\symbfit{oper_1 \leq oper_2 \leq \dots \leq oper_n}\)。
四边形不等式:对于任意的 \(\symbfit{a \leq b \leq c \leq d}\),有 \(\symbfit{val(a, c) + val(b, d)}\) 优于 \(\symbfit{val(a, d) + val(b, c)}\)。
1.3 一个小结论
如果一个 dp 函数 \(val\) 满足四边形不等式,那么这个 dp 具有决策单调性。
证明?不会。
标签:oper,symbfit,val,决策,leq,相关,单调 From: https://www.cnblogs.com/RB16B/p/18035082