1. 单调队列优化 DP
1.1 简介
当一个选手比你小还比你强，你就打不过他了。这是对单调队列简单形象的概括。
单调队列在转移的过程中不断排除不可能成为决策点的元素，使每次转移寻找决策点的时间复杂度降为 \(O(1)\)。一般地，可被单调队列优化的转移式可被写为如下形式：
\[F_i=\max_{l_i\le j<i}{F_j+A_j+B_i} \]\[（F_i=\min_{l_i\le j<i}{F_j+A_j+B_i}） \]其中需要满足 \(l_i\) 单调不降，\(A_i\) 是只与 \(i\) 有关的变量，\(B_j\) 是只与 \(j\) 有关的变量。
不难发现单调队列要维护的是 \(F_i+A_i\)，每次 \(j1\) 入队时，若满足 \(F_{j1}+A_{j1}>F_{j0}+A_{j0}\) 则将 \(j0\) 弹出，直到不满足条件或者队列为空。
此时取队头元素，它一定满足在范围内最优，将其作为决策点即可。特殊地，有时需要特判队列为空的情况。