一点关于 OI-wiki 上斜率优化 dp 的理解。

考虑一种可以写成 $b_i=\min_{j<i}\{y_j-k_ix_j\}$ 形式的转移，其中 $x_i,y_i$ 可以需要 $b_i$ 的值来确定并且 $k_i$ 递增。 此时把 $P_i:(x_i,y_i)$ 画出来，$b_i$ 的几何意义就是斜率为 $k_i$ 的直线过其中某个点的截距，不难得出这个点一定在 $P_{1\cdots i-1}$ 组成的下凸壳上，$k_i$ 卡在决策点与前后的斜率之间最优，于是在 dp 过程中维护下凸壳，得到 dp 值后加入末端，从前端取最优决策点转移。当然也有先建出凸壳再直接转移的题目。

带 $\log$ 的替代方式有李超线段树。

在转移不依赖于已求出的 dp 值时，例如 CF1715E，需要若干轮 $f_i=\min\{g_j+(i-j)^2\}$ 的转移，则可以先对 $P_j:(g_j,g_j+j^2)$ 建凸壳再转移，也可以进行若干轮决策单调性分治。

斜率优化 dp-摆渡车

题目链接。

设 $f_i$ 为最后一辆车在 $i$ 时刻出发的最小总花费。

令 $b_i$ 为 $[0,i]$ 时刻到达的人的 $t$ 的和，$s_i$ 为 $[0,i]$ 时刻到达的人数，$T=\max\{t_i\}$。

转移显然有当 $i\in[0,m)$，$f_i=i\times s_i-b_i$，当 $i\in[m,T+m)$，$f_i=\min_{j=0}^{i-m}\{f_j+i\times (s_i-s_j)-(b_i-b_j)\}$，则答案为 $\min_{i=T}^{T+m-1}\{f_i\}$。

前面的部分可以暴力算，考虑后面的转移，拆一下式子。

$f_i=i\times s_i-r_i+\min_{j=0}^{i-m}\{f_j+b_j-i\times s_j\}$，令 $w_i=f_i+b_i$，则后面需要最小化的东西是 $w_j-i\times s_j$。

考虑若在 $i$ 处转移时 $j$ 优于 $k$，则 $w_j-i\times s_j<w_k-i\times s_k,w_j-w_k<i\times(s_j-s_k),\frac{w_j-w_k}{s_j-s_k}<i$，记 $(j,k)$ 之间的斜率 $slope_{j,k}=\frac{w_j-w_k}{s_j-s_k}$。

我们发现当 $i$ 递增的时候对斜率的要求越来越放宽，所以可以维护一个斜率单调递增的下凸壳，转移 $i$ 时把 $i-m$ 放入队尾，转移时取队首（斜率最小）来转移，放一种自己用的实现方法。

int q[N],l=1,r=0;
bool check(int i,int j,int k){//check if slope(i,j)>=solve(j,k)
    return (w[i]-w[j])*(s[j]-s[k])>=(w[j]-w[k])*(s[i]-s[j]); 
} 
...
For(i,m,T+m-1){
    int j=i-m;
    //维护斜率单调递增的下凸壳
    while(l<r&&check(q[r-1],q[r],j))r--;//弹出影响斜率单调性的
    q[++r]=j;
    while(l<r&&(w[q[l]]-w[q[l+1]])>=i*(s[q[l]]-s[q[l+1]]))l++;//弹出当前看来转移不优的
    j=q[l];
    f[i]=f[j]+i*(s[i]-s[j])-(b[i]-b[j]),w[i]=f[i]+b[i];
}

不难发现每种状态只会加入一次队列，退出一次队列，时间复杂度 $O(T)$。