斜率优化 DP 学习笔记

· · 算法·理论

斜率优化 DP 通常可以写成基本形式：

dp_{i}=\max\{dp_j+w(i,j)\}

单调队列优化 DP 的 DP 转移式通常也可以写成如下形式，不同之处在于，单调队列优化 DP 时，w(i,j) 中通常只包含单独含 i,j 的项，因而可以将单独含 i 的项提出，将 dp_j 和单独含 j 的项看作一个整体放入单调队列之中；而 w(i,j) 通常包含 i,j 的乘积项，不好处理时，我们引入斜率优化 DP。

先入一个引理：应该略懂一些一次函数就没问题了吧。

若函数 f(x)=kx+b 经过两个点 (x_1,y_1),(x_2,y_2)，则该函数的斜率为 k=\dfrac{y_1-y_2}{x_1-x_2}。

然后上一道例题。

P3195 [HNOI2008] 玩具装箱

首先朴素 \mathcal{O(n^2)} DP 易得：

dp_i=\min\{dp_j+(i-j-1+s_i-s_j-L)\}

看着很不好拆括号，不妨设 a_i=i+s_i,b_i=i+s_i+L+1，则：

dp_i=\min\{dp_j+(a_i-b_j)^2\}

将 \min 去掉进行处理：

dp_i=dp_j+(a_i-b_j)^2

拆括号：

dp_i=dp_j+{a_i}^2-2a_ib_j+{b_j}^2

移项：

dp_j+{b_j}^2=2a_i\times b_j+(dp_i-{a_i}^2)

然后，将其看作 y=kx+b，即一次函数的形式，即：

y_j=dp_j+{b_j}^2 \\ k_i=2a_i \\ x_j=b_j\\ b_i=dp_i-{a_i}^2\\ \end{cases}

发现 k_i,b_i 为定值，而 x_j,y_j 为变量，每一个决策 j 则代表了坐标系上的点 (x_j,y_j)，这个式子表示了一条斜率为 2a_i 的直线。

也就是说也就是说假设我们用 j 转移，这条直线经过点 P_j(x_j,y_j) 时，它的截距加上 {a_i}^2 就是 dp_i。所以需要我们找到最优的 j 使得截距最小。（注：截距即 b_i。）

借用一下题解区的图：

如图，对于当前直线（图上红线），不断将其平移直到其碰到某一个决策点 j，此时截距最小，决策最优。

继续观察，不难发现对于任意直线最优决策点都一定在所有决策点的凸包上，也就是说我们只用维护凸包。考虑如何维护凸包：

记 slope(P_1,P_2) 表示经过点 P_1,P_2 的函数的斜率。首先知道凸包上的点 X_1,X_2,\dots,X_m 满足 slope(X1,X2)<slope(X2,X3)<\dots<slope(X_{m-1},X_m)。不妨用一个数组维护凸包上的点。设当前凸包上最后两个点分别为 X_{m-1},X_m，新加入一个点 P_i 时，若 slp(X_{m-1},X_m)>slp(X_m,P_i)，则应该把点 X_m 从凸包中删去，借用一下题解区的图：

如图，此时 X_m 就是典型的“上凸点”，应当去除以维护凸包单调性。

然后继续考虑如何在凸包上找到最优决策点。

记最优决策点为 X_i，其在凸包上面的前一个点记为 X_{i-1}，后一个点记为 X_{i+1}，画图可知一定有 slope(X_{i-1},X_i)<k<slope(X_i,X_{i+1})。

所以我们只需要找第一个使得 slope(X_i,X_{i+1})>k 的点 X_i 即可。通过二分维护即可。

然后整合一下各个部分就差不多了吧。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+5;
int n,S,L,R,s[N],a[N],b[N],dp[N],q[N];
int X(int x){return b[x];}
int Y(int x){return dp[x]+b[x]*b[x];} 
long double slp(int x,int y){return 1.0*(Y(x)-Y(y))/(X(x)-X(y));}//斜率 
int fd(int lt,int rt,long double k){//在决策点中二分 
    int ans=rt;
    while(lt<=rt){
        int mid=lt+rt>>1;
        if(slp(q[mid+1],q[mid])>k)rt=mid-1,ans=mid;
        else lt=mid+1;
    }
    return q[ans];
}
signed main(){
    cin>>n>>S;
    for(int i=1,x;i<=n;i++){cin>>x;s[i]=s[i-1]+x;}
    for(int i=0;i<=n;i++)a[i]=s[i]+i,b[i]=s[i]+i+S+1;
    L=R=1,q[R]=0;
    for(int i=1;i<=n;i++){
        int pos=fd(L,R,2.0*a[i]);//pos为最优决策点 
        dp[i]=dp[pos]+(a[i]-b[pos])*(a[i]-b[pos]);//用朴素的dp式子算答案即可(j=pos) 
        while(L<R&&slp(q[R],q[R-1])>=slp(i,q[R]))R--;//维护凸包 
        q[++R]=i;//维护凸包 
    }
    cout<<dp[n];
    return 0;
}

练习：