一类最优化 DP：
利用 \(w\) 的特殊性质，可以做到 \(O(n\log n)\) 或 \(O(n)\) 的复杂度
考虑对于每个未计算出的 \(f\)，维护其最优决策
即每算出一个 \(f_j\)，就把那些取决策 \(j\) 更优的 \(f_i\) 的最优决策更新成 \(j\)
由定义可知，需要更新决策的 \(i\) 一定是一段后缀
考虑用一个栈维护决策序列，对于每个决策 \(j\) 维护一个区间 \([l,r]\) 表示 \(f_{l\dots r}\) 的最优决策为 \(j\)
当 \(f_j\) 计算出来的时候，先考虑栈顶的 \(l\)，考查 \(f_j\) 能否更新 \(f_i\) 的最优决策
如果能就弹栈顶继续检查
否则在栈顶的区间 \([l,r]\) 中二分出一个最小的 \(i\) 满足 \(f_i\) 能被 \(f_j\) 更新最优决策
把 \(r\) 改成 \(i-1\)，并把决策 \(j\) 压入栈，区间为 \([i,n]\)
\(O(n\log n)\)
上面的方法存在一定的局限性：\(w(j+1,i)\) 必须能快速求出来
当 \(w(j+1,i)\) 必须以 \(O(i-j)\) 的复杂度求出时，考虑另一种实现方式：分治
定义分治函数 solve(l, r, xl, xr) 表示 \(f_{l\dots r}\) 的决策在 \([xl,xr]\) 之间
取 \(mid=\lfloor\frac{l+r}2\rfloor\)，求出 \(f_{mid}\) 的最优决策 \(m\)
然后递归到 solve(l, mid - 1, xl, m) 和 solve(mid + 1, r, m, xr)
还是 \(O(n\log n)\)
需要注意实现姿势，避免复杂度爆炸，保证单次分治的复杂度为 \(O(r-l+xr-xl)\)
但这种优化方法也有局限性：转移必须是 \(g\rightarrow f\) 而不能是 \(f\rightarrow f\)，即转移不能进行在同一个数组内
常用于分层 DP 中
\(w(j,i+1)-w(j,i)\) 和 \(w(j+1,i+1)-w(j+1,i)\) 的大小关系对于所有的 \(i,j\) 都一样，即满足四边形不等式
换句话说，对于任意的两个决策 \(j<k\)，存在一个 \(x\) 满足 \(i\le x\) 时 \(j\) 比 \(k\) 优，\(i>x\) 时 \(j\) 比 \(k\) 劣
或者 \(i\le x\) 时 \(j\) 比 \(k\) 劣，\(i>x\) 时 \(j\) 比 \(k\) 优
若 \(i\le x\) 时 \(j\) 比 \(k\) 优，\(i>x\) 时 \(j\) 比 \(k\) 劣，则这和前面提到的第一类是等价的，可以直接用第一类的优化方法
但这里讲述另一种方法
考虑维护一个单调队列，储存对当前的 \(i\) 和 \(i\) 之后可能最优的决策
每当计算出一个 \(f_l\) 之后，检查队尾的两个决策 \(j,k\) 是否会因为决策 \(l\) 的加入而使得 \(k\) 变成不可能最优的决策
根据定义里提到的特殊性质，我们只需二分出一个最大的 \(i\) 满足决策 \(k\) 比 \(l\) 优，然后判断这时 \(j\) 是否比 \(k\) 优，是则 \(k\) 应该被从队尾弹出
这样一直弹栈直到 \(k\) 可能最优为止
考虑取 \(f_i\) 最优决策，可以证明去除了无用的决策之后，队列内剩下的决策对应 DP 值是单峰的，故从队首不断出队即可找到最优决策
\(O(n\log n)\)
实际上判断是否弹队尾，有时可以使用特殊的方法代替二分来实现 \(O(1)\) 判断
如斜率优化的本质就是这种形式的决策单调性优化
若 \(i\le x\) 时 \(j\) 比 \(k\) 劣，\(i>x\) 时 \(j\) 比 \(k\) 优，则最优决策要从队尾取，这时把队列改成栈即可
原文：https://www.cnblogs.com/xyz32768/p/13055420.html