斜率优化 DP

xyzqwq · 2024-01-19 12:02:53 · 算法·理论

斜率优化是什么

对于一些形如

的 DP 转移式，我们经常使用单调队列优化，但考虑这样一种情形，假如 dp[i] 转移所依赖的项包括 i 和 j 的项，如

又该怎么办呢？

于是就有了斜率优化 DP。

斜率优化 DP。顾名思义，通过斜率来优化 DP（废话），以刚刚的 DP 式为例，假设现在已经 j 就是最好的转移点，我们来看这个转移的过程

由于是从 j 向 i 转移，所以此时我们可以把带 i 的项看成不动项，而把带 j 的项看成变量。

观察上面的 DP 转移式，很明显，这些项可以分成三种——带 i 的，带 j 的，以及既有 i 又有 j 的。

考虑一种数形结合的想法：令 y=dp[j],x=\text b[j]，这样就把转移式转化为了 b=y-kx 的形式。

如果我们想让 dp[i] 更小，那么就是要直线方程中的 b 更小，也就是截距更小。

如何让一条直线的截距更小呢？

把所有的 j 都按照刚刚的 x,y 表示成点（称之为决策点）。然后取一条斜率为 k 的直线上移逼近决策点，而后得到的 b=y-kx 就是最优的决策点。

如图，显然能够用直线逼近得到的最优决策点必定在下凸壳上，因此在下凸壳对 DP 值的更新就毫无用处，就不必再去维护，直接舍弃即可。

如何维护下凸壳呢？

如果斜率是单调递增的，显然可以用单调队列优化（如果不递增我们也有解决方案）。

首先，如果决策点用直线逼近不了，显然是要排除的。

而后是判凸包，如图

思考三个点 i,j,k 形成下凸壳的条件。

若给 i,j 和 j,k 连上直线，若三个决策点围成下凸壳 \iff K(i,j)<K(j,k)（其中 K 表示两点连线的斜率）。

这就解决了”什么时候排除决策点“的问题。斜率优化就变得 trival 了。

接下来以一道例题给出斜率优化 DP 的大致流程。

斜率优化 DP 的做题流程

现在假设你已经看出一道题是斜率优化 DP 了，你该怎样去做呢？

我们以 P3195 玩具装箱 一题为例。

首先，写出朴素的 DP 转移式，斜率优化 DP 是一种 DP 的优化，不知道 DP 式也就无法优化。

在本题中，很容易推出 DP 转移式

这个 DP 转移式是 O(n^3) 的，考虑前缀和优化，设 \mathrm C 的前缀和数组为 s[i]，于是得到了 O(n^2) 的 DP 转移式。

为方便转化，我们设 a[i]=s[i]+i,b[i]=s[i]+i+L+1，于是转移式变成

此时我们就可以开始斜率优化了，首先分类，写成 b=y-kx 的形式

在这里，y=dp[j]-b[j]^2,x=b[j],k=2a[i]。

斜率优化 DP 的代码中一般单独写出 x,y 的函数。

double X(int i){
    return b[i];
} 
double Y(int i){
    return dp[i]+b[i]*b[i]; 
}

而后还应有一个判斜率的函数，这里需要注意的是两点在同一 x 轴上的情况，这是我们规定前面点在后面点的下面时斜率为 +\infty，反之为 -\infty。

inline double K(int i,int j){
    if(X(i)==X(j)){
        if(Y(i)>Y(j)) return 1e18;
        return -1e18;
    }
    return 1.0*(Y(i)-Y(j))/(X(i)-X(j));
}

最后用单调队列维护这个下凸壳

    for(int i=1;i<=n;i++){
        while(h<t&&K(q[h],q[h+1])<2*a[i]) h++;//将不合法的决策点排除
        dp[i]=dp[q[h]]+(a[i]-b[q[h]])*(a[i]-b[q[h]]);//用当前最优的决策点更新 DP 值
        while(h<t&&K(q[t-1],q[t])>K(q[t],i)) t--;//将不在下凸壳上的决策点排除。
        q[++t]=i;//把当前点加入单调队列
    }

完整代码

接下来用几道例题加深我们对斜率优化 DP 的理解。

P2120 仓库建设

很容易推出本题的 DP 转移式

这个 DP 转移是 O(n^3)，考虑前缀和优化，设 s[i] 是 p_i 的前缀和，s2[i] 是 p_ix_i 的前缀和，于是 DP 转移式就化为了

和上一题一样，还是把相同项放到一起

这样就化成了 b=y-kx 的形式，直接斜率优化即可。

Code

P2365 任务安排

这一题有两种 DP 转移式，一种是 O(n^3) 的，可以通过斜率优化优化为 O(n^2)，还有一种直接推出 O(n^2) 的 DP 转移式，用斜率优化亦可优化至 O(n)。

我们首先考虑 O(n^3) 的做法，设 dp[i][j] 表示前 i 个任务分成 j 组得到的最小费用。

显然 DP 转移式为

考虑前缀和优化，设 sf[i] 是 f[i] 的前缀和，st[i] 是 t[i] 的前缀和，于是有了 O(n^3) 的 DP 转移式

由于这是一个二维 DP，所以我们把带 i,j 的项看成不变量，把 k 的项看成变量，再分类

这里让 y=dp[k][j-1]+sf[k]jS,x=sf[k]，就可以斜率优化了。

值得注意的是，二维 DP 的斜率优化中，需要交换 i，j 遍历的顺序，这是为什么呢？

形象地理解，每次进行转移时需要用到 j-1 的 DP 值，如果取 i 不动遍历 j 转移，得到的 DP 值就是错误的。反之固定 j 遍历 i，每次转移用到的上一个 j 是由正确的 i 得到的。

这样二维 DP 的斜率优化就与普通的斜率优化没什么区别了，记得每次遍历 j 时要重开单调队列，然后把 i,j 看成普通斜率优化的一个变量做。

Code

现在靠考虑 O(n^2) 的 DP 转移式，需要用到一种”费用提前“的思想。

由于本题并不限制分多少组，所以 j 这一维是多余的。

如何在 DP 转移式中去掉 j 呢？现在考虑分组数，每次多一个分组，后续的任务就会延误 S 秒，于是费用就多了 \sum_{l=k}^n f[l] ，所以只需要提前把费用加到 DP 值里，就不必计算 j 的贡献了。

于是就有了 O(n^2) 的 DP 转移式

按照斜率优化的套路，仍然把相同项放到一起

于是又可以快乐地斜率优化了。

Code

P4072 征途

这道题的式子比较智慧，首先写出方差的公式

设 S=\sum_{i=1}^m x_i，该式化为

题目要求的 m^2 s^2 即为

而 S^2 显然是定值，所以想要 s^2m^2 最小，就是要让 \sum_{i=1} ^m x_i^2 最小。

所以我们设 dp[i][j] 表示前 i 段走 j 天得到的最小方差。易推出 DP 转移式。

设 s[i] 是 a[i] 的前缀和，得到 O(n^3) 的 DP 转移式

移项

这又是一个二维的 DP 转移式，按照任务安排一题的 O(n^2) 的方法斜率优化即可。

Code

P3628 特别行动队

设 dp[i] 为前 i 个士兵的最大修正战斗力。

显然有 DP 转移式

设 s[i] 是 x_i 的前缀和数组，于是有

稍加整理

这就又是一个很可以斜率优化的 DP 式了。

不过你需要注意一件事，就是这题要求的是最大战斗力，取 \max，所以相应地维护的就变成了上凸壳，单调队列优化部分稍加改动即可。

Code

习题

1. P2900 Land Acquisition G

2. P3648 序列分割

3. P4360 锯木厂选址

CDQ 优化斜率优化 DP

重新思考斜率优化 DP，每次用得到的直线去切凸包得到最优的决策点，这个过程中直线的斜率肯定是单调递增的。

那么假如直线的斜率不递增了怎么办呢？

这时我们就要转换思路，直线的斜率不递增，但是凸包上点的斜率是递增的，这样凸包上点的斜率，和直线的斜率就构成了一对关系，每当有二者构成偏序的情况下就可以更新 DP 值。

这就有了处理方法，只要维护斜率的最值所对应的位置，就可以得到应当更新的斜率和决策点。

一般可以用平衡树或李超线段树进行维护。

还有一种更简明易想的方法——思考维护 DP 值的条件，必须要让切直线的斜率递增，也就是让决策点的斜率单增，如果做不到单增呢？

考虑我们都要维护那些顺序，首先是序号自然有序，而后还有每个决策点的 x 坐标，以及每个决策点对应的直线斜率。若有两个决策点 i,j，只有当 j 的这些条件都比 i 大时才能通过 j 更新 i 的 DP 值，也就是说 i 对 j 构成偏序，这就令我们想到了 CDQ 分治。

关于 CDQ 分治优化普通 DP ，可以看我的这篇博客。

CDQ 分治优化斜率优化 DP 也没什么区别，同样是处理左边对右边的贡献，接下来以一道例题给出 CDQ 分治优化斜率优化 DP 的大致流程。

P3195 玩具装箱

还是这道题，现在假设玩具的长度可以是负数，再来考虑这道题。

首先拿出当初我们推出的 DP 转移式

由于玩具长度是负数，所以前缀和数组 s[i] 就不再单增，而决策点的斜率 k_i=2a[i]=2(s[i]+i) 就也不再单增，所以按照刚刚写的，我们尝试 CDQ 分治。

首先还是按照一般的 CDQ 优化 DP 的套路，先处理左边对右边的贡献，此时要保证左边的 x 有序以更新右边，而后维护下凸壳，此时需要决策点的斜率有序，接下来和普通的斜率优化有些区别，我们需要先把左侧的决策点加入单调队列并排出右侧不合法的决策点。而后在处理左侧无用节点并更新 DP 值。

一些需要注意的细节

void merge(int l,int r){
    if(l==r){
        //直接把所有东西绑定在一起，避免频繁调用a[i].id
        a[l].x=B[l];
        a[l].y=a[l].dp+B[l]*B[l];
        return;
    }
    int mid=(l+r)/2;
    merge(l,mid);//向左走，并保证其按x有序以更新右边
    sort(a+mid+1,a+r+1,cmp3);//保证右边对k有序，以被左边更新
    int h=1,t=1;
    for(int i=l;i<=mid;i++){
        //把左侧的决策点加入单调队列，排除右侧不合法的决策点
        while(h<t&&K(q[t-1],q[t])>K(q[t],i)) t--;
        q[++t]=i;
    }
    for(int i=mid+1;i<=r;i++){
            //处理左侧无用节点，更新 DP 值
        while(h<t&&K(q[h],q[h+1])<a[i].k) h++;
        int ta=A[a[i].id];
        int tb=B[a[q[h]].id];
        a[i].dp=min(a[i].dp,a[q[h]].dp+(ta-tb)*(ta-tb));
    }
    sort(a+mid+1,a+r+1,cmp1);//让右边按id有序，从而让左右相对按id有序
    merge(mid+1,r);//向右走
    sort(a+l,a+r+1,cmp2);//最后按x有序，使上一层的分治过程正确
}

Code

P5785 任务安排2

这一题的数据范围和 P2365 的区别在于，时间 t_i 可能为负数。

分析刚刚的 DP 转移式

这里的斜率是 st[i]，也就是时间 t_i 的前缀和，在 P2365 中 t_i>0，所以 st[i] 单调递增。而这道题中不保证 t_i 的正负，决策点的斜率自然也就不单增了。

明白了这一点，就考虑优化，按照上一题的思路直接 CDQ 分治即可。

Code

P4655 Building Bridges

DP 转移式很容易推。

设 dp[i] 为连接第 1 根柱子和第 i 根柱子的最小代价。

显然有

设 s[i] 是 w[i] 的前缀和数组，于是得到了 O(n^2) 的 DP 转移式

现在就写成了一个可以斜率优化的形式。

显然决策点 i 的斜率是 2h[i]，显然不单调，于是 CDQ 分治。

Code

P2497 基站建设

设 dp[i] 为前 i 个基站的费用最小值，显然（）有 DP 转移式

这个分式看起来比较难优化，于是设一个 A[i]=\frac{1}{2\sqrt{r[j]}}，于是有

这里斜率是 A[i]，显然不单增，于是 CDQ 分治优化。

Code

习题

1. P4027 货币兑换

2. P7926 大胃王

3. P6302 回家路线 加强版