使用场景

状态 \(O(n)\)，转移 \(O(n)\)，只涉及 \(i,j\) 两个未知量，\(j\) 的取值范围的左、右端单调，可以把 \(f_i\) 当做截距维护上（max）、下（min）凸包。需要注意的是，它作用不仅仅可以优化 DP，本质是求某些最值，\(\color{red}\text{example}\)。

也可以在\(\color{pink}\text{一些题}\)中求斜率的最值，这时就是朴素的单调队列可以解决的。

以下只讨论 DP 中的应用，其他模型还需要靠灵光一闪去发现。

列式

设当前求 \(f_i\)，将只与 \(j\) 有关的项当做 \(y\)，交叉项为 \(kx\)，只与 \(i\) 有关的当做 \(b\)，得到一个一次函数解析式。

不交换 \(i,j\) 所表示的意义的原因：只知道所有 \((k,b)\) 和 \(x\)，求 \(y\) 的最值，这是李超树，没有单调性，时间最少 \(O(n\log n)\)。

1.不能斜优DP

条件

若 \(x\) 不单调，无法直接斜优。

感性理解

考虑维护凸包的过程，发现会涉及在中间插入值，就需要平衡树/set去实现。也可以改变定义，转为李超树。

强行斜优

发现这是在一个偏序问题中进行凸包维护加DP，可以离线+CDQ优化。先按 \(k\) 排序，再以 \(x\) 为关键字归并。要注意到前后的依赖关系：\(\text{左区间递归}\rightarrow\text{算贡献}\rightarrow\text{右区间递归}\)。

2.一般斜优DP

条件

\(x\) 单调。

目前只见过单调不降，但单调不增也是可以做的（应该差不多？）。

维护凸包，对斜率进行二分，找到一个分界点，即为决策点。

3.特殊斜优DP

条件

\(x\) 单调的同时 \(k\) 也单调。

这时有决策单调性，决策点在凸包上总是向一边移动的。这时可以使用单调数据结构进行维护。

可以根据取 \(min/max\)、\(x\) 单增/减、\(k\) 单增/减用单调栈/队列维护上/下凸包。