单调队列

扫盲贴:

单调队列是这样一种东西:

队列里面存放"决策"
队列需要维护一个连续时间范围内的最优决策
"过时"的决策将被弹出
队列元素的"时间戳"单调递增(即加入队列从队列尾部进行）
可知队列元素的"优性"(比如大小等..)递减
（简单证明：若队列元素a 在 b的左边 a没有b优。。那么在a没有出队列的时候b也肯定没有出队列
这样a 永无出头之日。。不可能成为后面某个时刻的最优决策了）

凸单调的1D/1D Dp:
f[i] = max/min { f[j] + w(i, j) } w(i, j)是凸的

g(a, b) 表示min{i | i > b > a 决策a没有决策b优，即决策b “追上了”决策a }
决策队列满足
g(i1, i2) < g(i2, i3) < ... (gik, gi(k+1) )
(一个决策一旦被另一个决策追上就永远不会优了..证明略 ^_^有兴趣的可以去翻书)
每到达一个时刻( 即i++ )
从队头开始把被追上的决策清理出去
然后队首的元素既是求f[i]的最优决策
同时将f[i]加入决策队列的队尾

伪代码:

qh = qt = 0
f[qh] = 0

for (int i=1;i<=n;i++) {
while (qh < qt && catch[qh+1] <= i) qh ++;
f[i] = F(i, q[qh]);
while (qh < qt && findcatchup(q[qt], i) <= catch[qt])
qt --;
catch[qt+1] = findcatchup(q[qt], i);
q[++qt] = i;
}