一点关于 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$ 的替代方式有李超线段树和决策单调性分治,后者看起来比较优秀。

例如 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)$。

最后修改:2022 年 08 月 25 日
如果觉得我的文章对你有用,请随意赞赏