动态规划（DP）——斜率优化

形如

d p [i] = m a x (d p [j] - a [i] \times b [j] + c [j]) + d [i]

的dp方程
（

a [x], b [x], c [x], d [x]

为一些与x有关的式子）
（需保证b[x]满足单调性）
如果是min，则后面的过程反过来，自己理解去。

为了 $O (1)$ 选出最优的j，假设 $d p [j]$ 优于 $d p [k]$ ，且 $b [j] > b [k]$
即，

d p [j] - a [i] \times b [j] + c [j] > d p [k] - a [i] \times b [k] + c [k]

变成

\frac{(d p [j] + c [j]) - (d p [k] + c [k])}{b [j] - b [k]} > a [i]

所以要求

\frac{(d p [j] + c [j]) - (d p [k] + c [k])}{b [j] - b [k]}

斜率越大越好，用单调队列维护
把上面那个

b [j]

当做横坐标，

(d p [j] + c [j])

当做纵坐标。
维护的单调队列要使斜率要递减（保证前面的更大），画成图像就成了一个上凸包：
动态规划（DP）——斜率优化

对于一个新的 $i$ ，保证 $b [i]$ 最大，队列的左边为 $h e a d$ ，判断head与head+1的斜率，如果head+1更优，即

\frac{(d p [h e a d + 1] + c [h e a d + 1]) - (d p [h e a d] + c [h e a d])}{b [h e a d + 1] - b [h e a d]} > a [i]

那么就head++;
所以

d p [i]

就从head位置转移过来。
接下来把

d p [i]

添加进单调队列，把队尾tail斜率比i小的全部弹出去，即

\frac{(d p [i] + c [i]) - (d p [t a i l] + c [t a i l])}{b [i] - b [t a i l]} > \frac{(d p [t a i l] + c [t a i l]) - (d p [t a i l - 1] + c [t a i l - 1])}{b [t a i l] - b [t a i l - 1]}

那么就tail--;
最后把i放进tail里。