发现别的人都对斜优很熟，就我不是（悲），所以写个小记辅助记忆一下。

1.应用范围

众所周知，单调队列优化 dp 可以解决形如 \(dp_i=val_i-val'_j\) 的问题

那么如果再加一个 \(val''_ival'''j\) 呢

这就要用斜率优化了。

2.方法

这东西非常灵活，所以直接上题目吧。

\(n\) 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 \(n\) 个任务被分成若干批，每批包含相邻的若干任务。

从零时刻开始，这些任务被分批加工，第 \(i\) 个任务单独完成所需的时间为 \(t_i\)。在每批任务开始前，机器需要启动时间 \(s\)，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。

每个任务的费用是它的完成时刻乘以一个费用系数 \(f_i\)。请确定一个分组方案，使得总费用最小。

先推一下式子：设 \(dp_i\) 为处理到 \(i\) 任务的最小费用， \(sumT\) 和 \(sumF\) 为 \(t\) 数组与 \(f\) 的前缀和。

转移方程为 \(dp_i=dp_j+s(sumF_n-sumF_j)+sumT_i(sumF_i-sumF_j)\) ，省去了 \(\min\)

~~其实已经可以过去了，但是还没用到斜优，不行~~

化一下式子： \((dp_i-sumT_isumF_i-s\cdot sumF_n)=(dp_j-s\cdot sumF_j)-sumT_isumF_j\)

如果没有最后这一个东西就可以直接上单调队列解决了

但是这依然是可做的。

前面这坨东西完全不受 \(j\) 影响，先不看，关键是后面的。

我们把用括号括着的那坨看成 \(b\) ， \(sumT_i\) 看成 \(k\) ，\(-sumF_j\) 看成 \(x\)

所以后面就是一个 \(kx+b\) 的形式。

这不就是一条直线吗！

我们把决策点看成 \((-x,b)\) ，然后把取决策看成用一条斜率为 \(k\) 的直线从下往上扫。

然后扫到一个点与 \(y\) 轴的交点坐标就是 \(kx+b\)

我们可以考虑维护一个下凸壳来搞这个东西。

具体来说，在单调队列里维护凸壳，每次加入一个点的时候，看当前队尾与前面的元素，如果不满足凸壳条件，则弹出队尾。

取最优决策的时候，在单调队列里二分一个决策，使得前面的斜率小于 \(k\) ，后面的斜率大于 \(k\) ，就满足这个从下往上扫。

在这个题目中， \(k\) 值单调，所以还可以通过弹出队头的方式，把复杂度优化到 \(O(n)\)

截止目前，本人今天在浏览器中敲了 \(3652\) 次键盘，鼠标点击了 \(282\) 次。