1维DP四边形不等式优化（决策单调性优化）

[giscus[bot]]

1维DP四边形不等式优化（决策单调性优化）

对序列切割问题，令 $f[i]=\smash{\displaystyle\min_{0 \le j \le i-1}} F(j, i)$，即 $1$ 到 $i$ 的最优解

https://coder114514.github.io/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0/2023/03/15/QI-opt.html

[coder114514]

求最小值： $w(j,i+1)-w(j.i) \le w(j-1,i+1)-w(j-1,i)$ 即 $w(j,i+1)+w(j-1.i) \le w(j-1,i+1)+w(j,i)$ aka 交叉<=包含
求最大值： $w(j,i+1)-w(j.i) \ge w(j-1,i+1)-w(j-1,i)$ 即 $w(j,i+1)+w(j-1.i) \ge w(j-1,i+1)+w(j,i)$ aka 交叉>=包含