斜率优化 dp

· · 算法·理论

原理

假设我们得到一个状态转移方程：

dp[i]=\min_{j=i-x}^{i-y}(dp[j]+a[i] \times b[j]+c[i]+d[j]+M)

发现与 i 有关的无法直接分离出来，直接单调队列优化做不了。

solve 1

我们换一种方法，考虑怎样比较 j_1,j_2(j_1 < j_2) 谁更优秀，显然满足下式时 j_2 更优秀：

dp[j_2]+a[i] \times b[j_2]+c[i]+d[j_2]+M \leq dp[j_1]+a[i] \times b[j_1]+c[i]+d[j_1]+M

我们将二次项集中在一边，另一边将与同一个下标有关的一次项放在一起：

-a[i](b[j_1]-b[j_2]) \leq (dp[j_1]+d[j_1])-(dp[j_2]+d[j_2])

当 b[j_1] \neq b[j_2]，上式等价于：

a[i] \geq \frac{(dp[j_1]+d[j_1])-(dp[j_2]+d[j_2])}{b[j_1]-b[j_2]}

那 b[j_1] = b[j_2] 呢？我们引进复数域黎曼球里的概念，认为 \dfrac{(dp[j_1]+d[j_1])-(dp[j_2]+d[j_2])}{0}=\infty（炸裂）。至于实现嘛，我们待会再说。

令函数 X(j)=b[j],Y(j)=dp[j]+d[j]，上式等价于：

a[i] \geq \frac{Y(j_1)-Y(j_2)}{X(j_1)-X(j_2)}

将 (X(j),Y(j)) 作为 j 在平面直角坐标系中的对应点，上式等价于 j_1,j_2 对应点所构成的直线斜率小于等于 a[i] 时，决策点 j_2 一定优于 j_1。

假设 j \in [i-x,i-y] 所对应的散点如下图所示：

先只关注 P_1,P_2,P_3 三个点和他们构成的直线的斜率 k_1,k_2(k_1>k_2)。

我们发现，无论 a[i] 如何变化，P_2 都不可能是最优决策点。

推广一下：如下图所示，可能作为最优决策点的点一定在这些散点的下凸包上。

进一步地，因为下凸包斜率单调递增，如果下凸包上一点 P_j 前面的下凸包上的斜率全部小于等于 a[i] ，后面的下凸包上的斜率全部大于 a[i]，根据我们刚才的分析易得 j 为最优决策点。

如图所示，对于某一个斜率 a[i] 而言，它的最优决策点应当是 j \in [i-x,i-y] 满足直线 P_{j-1}P_{j} 的斜率 k \leq a[i] 的最大的 j。

当然，如果上面的式子是 a[i] \leq \dfrac{Y(j_1)-Y(j_2)}{X(j_1)-X(j_2)}，最优决策点就应该是在上凸包上，其他的分析过程基本相同，这里不作赘述。

solve 2

先复习一下一开始的式子：

dp[i]=\min_{j=i-x}^{i-y}(dp[j]+a[i] \times b[j]+c[i]+d[j]+M)

先把 \min 去掉：

dp[i]=dp[j]+a[i] \times b[j]+c[i]+d[j]+M

把只与 j 有关的放在等式的左边：

dp[j]+d[j]=-a[i] \times b[j]+dp[i]-c[i]-M

令 y=dp[j]+d[j],k=-a[i],x=b[j],b=dp[i]-c[i]-M，上式就变成了一次函数解析式 y=kx+b，最小化 dp[i] 就等价于最小化 b。

这里移项的原则其实是：

其他的你就随便移项就好了。

将上式的 x,y 作为 j 在平面直角坐标系上对应的点（不难发现，我们整理式子的原则就是这些位置整得只与 j 有关）。

现在的最优决策点就是拿斜率 k=a[i] 的直线去卡每个点（也可以想象成从下方无穷远的地方往上推），找经过哪个点对应的 b 最小。

由图可知，最优决策点依然在下凸包上，并且位置就在 solve 1 中提到的对于 j \in [i-x,i-y] 满足直线 P_{j-1}P_{j} 的斜率 k \leq a[i] 的最大的 j。

同样的，如果是最大化 b 就是上凸包了。

solve 1 & solve 2

其实它们本质是相同的，可以相辅相成地来理解。

接下来，明白了最优决策点在什么位置，那该怎么快速地找最优决策点呢？

  1. 如果状态转移决策具有决策单调性（放在刚才的例子里就是 \forall i>j,a[i]>a[j]，即二次项系数 a[i] 单调递增，此时随着和斜率比较的 a[i] 的不断增加，由于下凸包上的点单调递增，a[i] 卡到下凸包上的点一定越来越靠后），则可以用单调队列维护凸包上的点。

  2. 如果不具有决策单调性，则根据凸包的单调性二分即可。

总结

这就是斜率优化的基本原理了，再看一遍它的模板状态转移方程：

dp[i]=\min_{j=i-x}^{i-y}(dp[j]+a[i] \times b[j]+c[i]+d[j]+M)

至于实现就跟着例题来说吧。

例题

P3195 [HNOI2008] 玩具装箱

玩具第一次装箱祭。

分析

显然设 dp[i] 表示从第 1 个玩具放到第 i 个玩具的最小花费。

读完题目，能够推出暴力的状态转移方程：

dp[i]=\min_{j=1}^{i-1}(dp[j]+((\sum_{k=j+1}^{i}C_k)+j-i-L)^2)

令 S_i=(\sum_{j=1}^{i}C_j)+i,M=L+1 得：

dp[i]=\min_{j=1}^{i-1}(dp[j]+(S_i-S_j-M)^2)

把平方拆开得：

dp[i]=\min_{j=1}^{i-1}(dp[j]+S_i^2+S_j^2+M^2-2S_iS_j-2S_iM+2S_jM)

看到 2S_iS_j 这一项，斜率优化没跑了。

这个题我先用 solve 1 的方法推一下，下个题再用 solve 2 的方法。

暴推式子

$$dp[j_2]+S_i^2+S_{j_2}^2+M^2-2S_iS_{j_2}-2S_iM+2S_{j_2}M \leq dp[j_1]+S_i^2+S_{j_1}^2+M^2-2S_iS_{j_1}-2S_iM+2S_{j_1}M$$ $$\Leftrightarrow dp[j_2]+S_{j_2}^2-2S_iS_{j_2}+2S_{j_2}M \leq dp[j_1]+S_{j_1}^2-2S_iS_{j_1}+2S_{j_1}M$$ 整理得： $$-2S_i(S_{j_1}-S_{j_2}) \geq (dp[j_2]+S_{j_2}^{2}+2S_{j_2}M)-(dp[j_1]+S_{j_1}^{2}+2S_{j_1}M)$$ 即： $$2S_i(S_{j_1}-S_{j_2}) \geq (dp[j_1]+S_{j_1}^{2}+2S_{j_1}M)-(dp[j_2]+S_{j_2}^{2}+2S_{j_2}M)$$ $$\because C_i \geq 1,j_1 \neq j_2$$ $$\therefore S_{j_1} \neq S_{j_2}$$ $$\therefore 2S_i \geq \dfrac{(dp[j_1]+S_{j_1}^{2}+2S_{j_1}M)-(dp[j_2]+S_{j_2}^{2}+2S_{j_2}M)}{S_{j_1}-S_{j_2}}$$ 令 $X(j)=S_{j},Y(j)=dp[j]+S_{j}^{2}+2S_{j}M$，得： $$2S_{i} \geq \dfrac{Y(j_1)-Y(j_2)}{X(j_1)-X(j_2)}$$ 满足此条件时有 $j_2$ 优于 $j_1$，则根据 _原理_ 处的推导，只需要维护 $j \in [1,i-1]$ 对应的点集 $(X(j),Y(j))$ 的下凸包即可。 又由于 $S_i$ 单调递增，所以状态转移具有决策单调性，可以用单调队列维护，已经不是 $i$ 的最优决策点的点不会再是 $i+1$ 的最优决策点（关键在于自己结合前面的式子思考一下）。 注意： - 单调队列中维护凸包上的点对应的 $j$。 - 维护的点不应存在三点共线，而应当只维护两端点。 - 单调队列中应保证至少有两个点再求斜率，deque 难以实现且常数大，建议使用手写队列。 - 维护凸包比较斜率时建议不要使用除法，容易被卡精度，交叉相乘是更好的选择。同时， $\dfrac{a}{0} \geq \dfrac{b}{c}$ 交叉相乘后恒成立，这难道不正是我们一直在找的 $\dfrac{a}{0}=\infty$ 的可行实现方案吗？ 做完这一通，你就会发现：solve 1 推式子还可以，但是上 or 下凸包的分析不（你）是（得）很（自己）直（画）观（图），优势是推出来的东西直接就能写代码，写起来很方便。 ### AC CODE ```cpp #include<bits/stdc++.h> using namespace std; int n; long long M; long long a[100005]; long long sum[100005]; long long dp[100005]; int q[100005]; long long X(int j){ return sum[j]; } long long Y(int j){ return dp[j]+sum[j]*sum[j]+2*sum[j]*M; } long long up(int i,int j){ return Y(j)-Y(i); } long long down(int i,int j){ return X(j)-X(i); } int main(){ cin>>n>>M; M++; for(int i=1;i<=n;i++){ cin>>a[i]; sum[i]=sum[i-1]+a[i]+1; } int h=0,t=0; q[t]=0; for(int i=1;i<=n;i++){ while(h<t&&2*sum[i]*down(q[h],q[h+1])>=up(q[h],q[h+1])) h++; dp[i]=dp[q[h]]+(sum[i]-sum[q[h]]-M)*(sum[i]-sum[q[h]]-M); while(h<t&&up(q[t],i)*down(q[t-1],q[t])<=up(q[t-1],q[t])*down(q[t],i)) t--; q[++t]=i; } cout<<dp[n]<<"\n"; return 0; } ``` ## [AT_dp_z Frog 3](https://www.luogu.com.cn/problem/AT_dp_z) ### 分析 依旧是设 $dp[i]$ 表示跳到第 $i$ 块石头上的最小花费。 题目里给出了状态转移方程： $$dp[i]=\min_{j=1}^{i-1}((h_i-h_j)^2+C)$$ 又是斜优没跑了……这里用 solve 2 里的方法推一下式子。 ### 暴推式子 把 $\min$ 去掉，平方拆开： $$dp[i]=h_i^2+h_j^2-2h_{i}h_{j}+C$$ 按照上文说的，将只含 $j$ 的项放一边： $$h_j^2=2h_{i}h_{j}+dp[i]-h_i^2-C$$ 令 $y_j=h_j^2,k=2h_i,x_j=h_j,b=dp[i]-h_i^2-C$，这又变成了一个过 $(x_j,y_j)$ 的一次函数解析式求 $b$ 最小值的问题，依旧是维护下凸包，将 $j$ 抽象成平面直角坐标系上的点 $(x_j,y_j)$ 即可。 本题保证 $h_i$ 单调递增，故具有决策单调性，单调队列维护下凸包即可，当前位置 $i$ 的最佳决策点是下凸包上第一个斜率大于 $h_i$ 的直线的左端点（最后一个斜率小于等于 $h_i$ 的直线的右端点），图像想起来很直观。 solve 2 这样式子推得很直观，图像（上 or 下凸包）想起来也很方便，但是体现在代码语言里的就太少了，写代码的时候还得参考一下 solve 1。 ### AC CODE ```cpp #include<bits/stdc++.h> using namespace std; int n; long long M; long long a[200005]; long long dp[200005]; int q[200005]; long long X(int j){ return a[j]; } long long Y(int j){ return dp[j]+a[j]*a[j]; } long long up(int i,int j){ return Y(j)-Y(i); } long long down(int i,int j){ return X(j)-X(i); } int main(){ cin>>n>>M; for(int i=1;i<=n;i++){ cin>>a[i]; } int h=0,t=0; q[t]=1; for(int i=2;i<=n;i++){ while(h<t&&2*a[i]*down(q[h],q[h+1])>=up(q[h],q[h+1])) h++; dp[i]=dp[q[h]]+(a[i]-a[q[h]])*(a[i]-a[q[h]])+M; while(h<t&&up(q[t],i)*down(q[t-1],q[t])<=up(q[t-1],q[t])*down(q[t],i)) t--; q[++t]=i; } cout<<dp[n]<<"\n"; return 0; } ``` ## 任务安排全家桶 ### 题目链接 #### [P2365 任务安排 1](https://www.luogu.com.cn/problem/P2365) #### [P10979 任务安排 2](https://www.luogu.com.cn/problem/P10979) #### [P5785 任务安排 3（[SDOI2012] 任务安排 ）](https://www.luogu.com.cn/problem/P5785) ### 前言 这三个题只在数据范围略有不同，~~我是不会告诉你第三题的代码能过所有的~~，根据不同的数据我们要选择合适的做法。 ### 分析 先设 $dp[i]$ 表示已经完成了前 $i$ 个任务的花费。你会发现，题目中的 $s$ 难以进行处理，这里用到一个很典的思路，统计当前对后面的影响（后面难以统计前面的贡献，那么就在前面对后面有贡献的时候直接累加在前面的值上），状态的定义就这样略有变化。 再前缀和优化一下，$st[i]=\sum_{j=1}^{i} t_j,sc[i]=\sum_{j=1}^{i} c_j$。 这样一来状态转移就相当简单了： $$dp[i]=\min_{j=1}^{i-1}(dp[j]+st[i] \times (sc[i]-sc[j])+s \times (sc[n]-sc[j]))$$ 表示在 $j$ 和 $j+1$ 之间分开，第 $i$ 件物品做完，不计算 $s$ 的截止时间 $st[i]$ 乘上每个物品的花费。同时完成 $j+1$ 到 $n$ 的总时长都要在 $st$ 数组的基础上再加上这一次启动机器的时间 $s$，还要再额外花费 $s \times (sc[n]-sc[j])$。 这样的时间复杂度是 $O(n^2)$ 的，你会发现可以过掉[P2365 任务安排 1](https://www.luogu.com.cn/problem/P2365)。 注意：$0$ 和 $1$ 之间可以进行分割，$j$ 从 $0

开始枚举。

code of P2365 任务安排 1

#include<bits/stdc++.h>
using namespace std;
int n;
long long M;
long long c[300005],t[300005];
long long sc[300005],st[300005];
long long dp[300005];
int main(){
    memset(dp,0x3f,sizeof dp);
    cin>>n>>M;
    for(int i=1;i<=n;i++){
        cin>>t[i]>>c[i];
        st[i]=st[i-1]+t[i];
        sc[i]=sc[i-1]+c[i];
    }
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            dp[i]=min(dp[i],dp[j]+st[i]*(sc[i]-sc[j])+M*(sc[n]-sc[j]));
        }
    }
    cout<<dp[n]<<"\n";
    return 0;
}

进一步地分析

状态转移方程中有含 i 项与含 j 项的乘积，斜率优化没跑了。

把 \min 去掉并拆括号得：

dp[i]=dp[j]+st[i] \times sc[i]-st[i] \times sc[j]+s \times sc[n]-s \times sc[j]

移项得：

dp[j]=(st[i]+s) \times sc[j]+dp[i]-st[i] \times sc[i]-s \times sc[n]

令 y=dp[j],k=st[i]+s,x=sc[j],b=dp[i]-st[i] \times sc[i]-s \times sc[n]，一定要保证 b 中不含关于 j 的项，因为这样才能将问题转化为最小化 b。

如果将 j 在平面直角坐标系中对应的点设为 (x,y)。问题就转化成了拿斜率为 k 的线去卡每个点，最小化截距 b。

易知最优决策点是下凸包上最后一个斜率小于等于 k 的右端点。

在P10979 任务安排 2中，t_i \geq 1，所以 st[i] 单调递增，进而 k=st[i]+s 单调递增，如果下凸包上某两个点构成的直线的斜率已经不是 i 前面最大的小于等于 st[i]+s 的斜率，由于 st[i+1]+s>st[i]，所以该直线的右端点也不可能作为 i+1 的最优决策点。这种特性使得本题可以使用单调队列在维护下凸包的同时维护 i 的最优决策点。

code of P10979 任务安排 2

#include<bits/stdc++.h>
using namespace std;
int n;
long long M;
long long c[300005],t[300005];
long long sc[300005],st[300005];
long long dp[300005];
int q[300005];
long long X(int j){
    return sc[j];
}
long long Y(int j){
    return dp[j];
}
long long up(int i,int j){
    return Y(j)-Y(i);
}
long long down(int i,int j){
    return X(j)-X(i);
}
int main(){
    cin>>n>>M;
    for(int i=1;i<=n;i++){
        cin>>t[i]>>c[i];
        st[i]=st[i-1]+t[i];
        sc[i]=sc[i-1]+c[i];
    }
    int h=0,t=0;
    q[t]=0;
    for(int i=1;i<=n;i++){
        while(h<t&&down(q[h],q[h+1])*(st[i]+M)>=up(q[h],q[h+1])) h++;
        dp[i]=dp[q[h]]+st[i]*(sc[i]-sc[q[h]])+M*(sc[n]-sc[q[h]]);
        while(h<t&&up(q[t],i)*down(q[t-1],q[t])<=up(q[t-1],q[t])*down(q[t],i)){
            t--;
        } 
        q[++t]=i;
    }
    cout<<dp[n]<<"\n";
    return 0;
}

而在P5785 任务安排 3（[SDOI2012] 任务安排 ）中，t_i 可能为负，所以 st[i]+s 不具有单调性。我们就需要记下来 i 前面的点的下凸包上的所有点，根据凸包上斜率的单调性进行二分。

code of P5785 任务安排 3（[SDOI2012] 任务安排 ）

#include<bits/stdc++.h>
using namespace std;
int n;
long long M;
long long c[300005],t[300005];
long long sc[300005],st[300005];
long long dp[300005];
int q[300005];
long long X(int j){
    return sc[j];
}
long long Y(int j){
    return dp[j];
}
long long up(int i,int j){
    return Y(j)-Y(i);
}
long long down(int i,int j){
    return X(j)-X(i);
}
int binary_search(int l,int r,long long k){
    int mid=0;
    while(l<r){
        mid=(l+r)>>1;
        if(up(q[mid],q[mid+1])<=down(q[mid],q[mid+1])*k){
            l=mid+1;
        }else{
            r=mid;
        }
    }
    return q[l];
}
int main(){
    cin>>n>>M;
    for(int i=1;i<=n;i++){
        cin>>t[i]>>c[i];
        st[i]=st[i-1]+t[i];
        sc[i]=sc[i-1]+c[i];
    }
    int top=1;
    q[top]=0;
    for(int i=1;i<=n;i++){
        int j=binary_search(1,top,M+st[i]);
        dp[i]=dp[j]+st[i]*(sc[i]-sc[j])+M*(sc[n]-sc[j]);
        while(top>1&&up(q[top],i)*down(q[top-1],q[top])<=up(q[top-1],q[top])*down(q[top],i)){
            top--;
        } 
        q[++top]=i;
    }
    cout<<dp[n]<<"\n";
    return 0;
}

Thanks For Your Reading!