一个方程：

\[f_i = \min_{j=1}^{i-1}{\{f_j+w_j*l_i\}}\]

附加条件：\(w_j\) 单调递减，\(l_i\) 单调递增。

考虑固定 \(j\)，写出 \(f_i\) 随 \(i\) 的关系，观察到如果令 \(k=w_j,b=f_j\) ，则 \(f_i\) 与 \(l_i\) 成一次函数关系，并且随 \(j\) 的增加，这些直线的斜率单调递减。在同一直角坐标系中作出它们的图线，大概是这样的：

而我们最后会对所有 \(j\) 的答案进行一个 \(\min\) 的取，所以真正有用的是上图中的红色部分。

众所周知，斜率优化会用到单调队列，所以对出队和入队进行分析。

出队：

现在假设我们队列里有如图三条斜着的直线，而绿色的那条直线是当前的 \(l_i\) 。

对于队首的第一条直线，它和第二条直线的交点小于当前的 \(l_i\) ，第二条直线斜率又比它大，于是它成为了时代的眼泪，于是我们把它 pop 掉。

入队：

假设现在往队尾插入橙色直线。

我们发现橙色直线和队尾直线的交点比队尾直线和倒数第二条直线的交点要靠前，于是橙色直线就覆盖掉了队尾直线的所有优势区间，于是我们把队尾 pop 掉，把橙色直线塞进去。

于是可以用队首转移。

搬运自 Luogu Blog