斜率优化dp总结

斜率优化dp

前言：

我们学过不少优化类的算法了，大部分都是基于凸函数的性质给出的优化，比如Slope Trick，Wqs二分，又比如今天的斜率优化（不知道什么时候会有空把Slope Trick写掉）

正文：

我们考虑一类比较常见的dp方程：$dp_i=min/max_{j}(a_i*b_j+c_j+d_i)$,其中$b_j是单调增的$$（事实上b_j$不单调增也可以用斜率优化处理，但是这里我们为了简化先考虑这样一种特殊情况）。同时，为了方便，接下来我们先以min为讨论对象，实际上max是同理的，读者可以自己对应手推一遍

一般的暴力递推，复杂度是$O(N^2)$的。

我们考虑改变一下式子的形式：$dp_i=min_{j}\{a_i*b_j+c_j\}+d_i$,此时对于固定的$i$,外面的$d_i$是固定的，所以我们真正要考虑的其实是$a_i*b_j+c_j$这样一个式子的最小值，它其实就是一个一次函数$kx+b$的形式，其中$k=b_j,b=c_j$。我们不妨记$f_{i,j}=a_i*b_j+c_j$

凸包

我们不妨来看一下，如果两个点$x<y$，对于某一个i满足$f(i,y)\leq f(i,x)$,也就是说$y$是比$x$更加优的一个决策点，它们之间会有什么关系

$f(i,y)=a_i*b_y+c_y\leq f(i,x)=a_i*b_x+c_x$

即：$\large \frac{c_y-c_x}{b_y-b_x}\leq -a_i$(注意之前我们假定$b_i$是单增的)

这里是在做一个参变分离，注意这里我们其实是将x,y的信息视为已知量，而将i作为变量

放到二维坐标系下考虑，就是$(b_x,c_x),(b_y,c_y)$两个点的连线的斜率$\leq -a_i$

换句话说，这里如果x是y之前的比较优的一个点，在y出现之后它就被淘汰了，判断的条件我们记为$k_{xy}<=K(X)$,其中$K(X)=-a_i$。

接着我们将考虑的点数扩大到三个点$x\leq y \leq z$,这里我们不妨先限定$K_{yz}\leq K_{xy}$

边界条件还是$K(X)=-a_i$

按照之前的讨论，对于两个点$x,y$,若$k_{x,y}\leq K(x)$,则点$y优于x$,否则$点x优于y$

那么我们有如下几种情况：

$K_{yz}<K_{xy} K(X) $,则$点z优于点x,y$
$K_{yz}\leq K(X)<K_{xy}$,则点$x,z$优于$点y$
$K(X)\leq K_{yz}<K_{zy}$,则点x优于点$y,z$

此时我们惊奇地发现，不管是哪一种情况，点$y$都不可能作为最优解。按照之前所说，我们其实是对于这样一系列固定的点，对于不同的i，考察最优决策点的变化。也就是说，如果我们提前处理好了这样若干个点，那么我们就已经知道点y永远不会成为最优决策点了（在三个点都能选择的情况下）

讲回我们在这部分讨论前做的假设$K_{yz}\leq K_{x,y}$,读者可以自行验证，当三点不满足该关系的时候，我们并不能得到类似或者什么更优的结论。

那么我们对于一个固定的点i，将所有能进行决策的点进行这样一个预处理过程的话（大部分情况下对于固定的点i，我们只能够在$[1,i-1]$内决策，这里直接取该情况，其它情况其实同理），$\forall 1\leq x<y<z< i$,若$K_{yz}\leq K_{x,y}$,则将点y删除（因为它永远不会成为一个最优）,那么将留下来的点两两按横坐标顺序前后链接，斜率是单调不降的，换句话说，留下来的点就形成了一个下凸包，如下图所示，其中绿色连接部分就是一个凸包，红色点是在处理过程中被删除的点

最优决策点的快速寻找

一旦要维护的东西变成了一个凸包，那么我们的手段就可以很骚了，因为此时它的斜率具有单调性，我们就可以上二分等手段了 :)

对于一个固定的i，我们有$K(X)=-a_i$,由于下凸包的斜率是单增的，所以将斜率从左到右一一写出来的话，我们会得到如下关系

$K_1<K_2<...<K_s\leq K(X)<K_{s+1}...K_{m}$

那么我们要找的点显然就是s，也就是最后一个与前面的点连线的斜率$\leq K(X)$的点

那么我们维护好这个凸包之后，直接用二分线段即可，最后一个斜率$\leq K(X)$的线段的右端点就是答案了

考虑凸包的一个特殊情况：多个点处于一条线段上，就如上图的第二条线段，但是该情况对我们的选择并没有影响，因为我们取的是每一个线段的最右端点

这样每次去寻找最优决策点的复杂度是$O(log)$的，再加上维护凸包的复杂度$O(N)$,时间复杂度就是$O(NlogN)$的

具体流程:

A 在凸包上二分找到最优决策点x
B 用x的值更新$dp_i$
C 在将i加入凸包之前，我们要先将队尾一部分一定没有i优的点踢掉，然后再将i加入凸包

对步骤C的解释：这里将i直接加入凸包的话，有可能我们维护的就不再是一个凸包了，如下图情况

不难发现，此时$x,y,i$三点形成的就是之前讨论过的三个点的情形，所以y是一定不会成为最优决策点的。同理，踢掉y之后，如果$z,x,i$也是一个情况的话，x也会被踢掉，直到最后不再有这样的点为止

再优化

注意到上面的复杂度还是有点高，我们考虑dp过程中常见的决策单调性情况

决策单调性：在dp过程中，设$S_i表示dp_i$的最优决策点，如果$\forall i<j,S_i\leq S_j$则称该dp过程满足决策单调性，也就是说随着dp过程的进行，最优决策点是单调不降的

关于决策单调性的证明，常见的就是四边形不等式，这里暂且不提，后面有空再说:)

决策单调性在这里意味着什么？意味着之前已经被淘汰的点是不会再作为最优决策点出现的。所以我们就可以考虑用单调队列来维护。

具体流程：

A 将队列首部斜率$\leq K(X)$的线段的左端点不断踢出，最后剩下的队首元素x就是最优决策点。（正确性显然）
B 用x的值更新$dp_i$
C 在将i加入凸包之前，我们要先将队尾一部分一定没有i优的点踢掉，然后再将i加入凸包

与直接二分的区别就在于步骤A

同时我们注意到，如果$K(X)$是单调的，其自然满足决策点的单调性。（在横坐标单调的前提下）

类型总结（单调队列维护凸包）

当dp式子满足$\large \frac{c_y-c_x}{b_y-b_x}\leq -a_i$的时候，我们要维护的是一个下凸包

ll hd=1,tl=0;
que[++tl]=0;
for(int i=1;i<=n;++i)
{
    while(hd<tl&&Slope(que[hd],que[hd+1])<=k[x]) hd++;//这里k[x]表示K(X)
    dp[i]=...//用que[hd]来更新dp[i]即可
    while(hd<tl&&Slope(que[tl-1],que[tl])>=Slope(que[tl],i)) tl--;
    que[++tl]=i;//插入凸包
}

当dp式子满足$\large \frac{c_y-c_x}{b_y-b_x}\geq -a_i$的时候，同理就是维护一个上凸包

ll hd=1,tl=0;
que[++tl]=0;
for(int i=1;i<=n;++i)
{
    while(hd<tl&&Slope(que[hd],que[hd+1])>=k[x]) hd++;//这里k[x]表示K(X)
    dp[i]=...//用que[hd]来更新dp[i]即可
    while(hd<tl&&Slope(que[tl-1],que[tl])<=Slope(que[tl],i)) tl--;
    que[++tl]=i;//插入凸包
}

Tip

当两个点的横坐标相等的时候，实际上不存在斜率，这里我们要特判，取为inf
到底维护的是上凸包还是下凸包不要弄混，仔细推导一遍最好
一般是直接用double类型来计算斜率并进行比较，但是有时候出题人不讲武德卡精度，那就要转成乘式类型来比较了，这时候要注意一下负号改变方向的情况
队列一开始要放进去一个0，毕竟也不一定非有上一个转移点
有时候dp值会需要预处理，要小心
比较斜率的时候最好使用$\leq,\geq$

一些特殊情况

$b_j$是单调减的：实际与之前的情况同理。在一开始的推导中我们假定$x<y$，本质上就是为了保证$b_j$是单增的，如果此时它是单减的，我们只要在原本的式子中在对应位置取负，再改变前面符号，重新推导即可。此时$-b_j$就是单增的了
$b_j$不具备单调性：此时我们不能直接通过单调队列来维护凸包，因为新加入的点的横坐标并不是单调的，可能会插入在凸包的中间的位置。此时需要采用cdq分治
不具备决策单调性：那就只能二分了，不能强行弹出点，因为它可能在后面会成为最优决策点
不具备决策单调性&横坐标不单调：cdq分治后面会讲

例子

仓库建设

大意：

$n$ 个工厂，由高到低分布在一座山上，工厂 $1$ 在山顶，工厂 $n$ 在山脚。第 $i$ 个工厂目前已有成品 $p_i$ 件，在第 $i$ 个工厂位置建立仓库的费用是 $c_i$。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，产品只能往山下运（即只能运往编号更大的工厂的仓库），一件产品运送一个单位距离的费用是 $1$。

工厂 $i$ 距离工厂 $1$ 的距离 $x_i$（其中 $x_1=0$）。
工厂 $i$ 目前已有成品数量 $p_i$。
在工厂 $i$ 建立仓库的费用 $c_i$。

问修建仓库的最小代价

思路：

设$dp_i$表示前i个工厂的最小代价，写出dp式子的过程还是比较套路的，

$dp_i=min_{j\leq i}\{dp_j+x_i\sum_{k=j+1}^{i}(p_k)-\sum_{k=j+1}^{i}(x_kp_k) \}+c_i$

转化得到

$dp_i=min_{j\leq i}\{dp_j+x_i(sum_i-sum_j)-(xsum_i-xsum_j)\}+c_i$

其中$sum_i=\sum_{k=1}^{i}p_k,xsum_i=\sum_{k=1}^{i}p_k*x_k$

所以$dp_i=min_{j\leq i}\{-sum_jx_i+(dp_j+xsum_j)\}+x_isum_i-xsum_i+c_i$

这里$sum_j$是单调增的

考虑$a<yb$,且b优于a:

令$f_j=dp_j+xsum_j$

$-sum_bx_i+f_b\leq -sum_ax_i+f_a$

$\frac{f_b-f_a}{sum_b-sum_a}\leq x_i$,这里我们要维护的就是一个下凸包了，并且斜率$K(X)=x_i$是单调增的

因此直接套板子即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll N=1e6+10;
const ll inf=1e18;
struct ty
{
    ll x,p,c;
}mas[N];
ll sum[N];
ll xsum[N];
ll n;
ll dp[N];
ll que[N];
ll gt(ll l,ll r)
{
    return mas[r].x*(sum[r]-sum[l])-(xsum[r]-xsum[l]);
}
double Slope(ll a,ll b)
{
    if(sum[a]==sum[b]) return inf;
    double x=(dp[a]+xsum[a]-dp[b]-xsum[b])*1.0;
    double y=(sum[a]-sum[b])*1.0;
    return x/y;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>mas[i].x>>mas[i].p>>mas[i].c;
    for(int i=1;i<=n;++i) sum[i]=sum[i-1]+mas[i].p,xsum[i]=xsum[i-1]+mas[i].x*mas[i].p;
    ll hd=1,tl=0;
    que[++tl]=0;
    for(int i=1;i<=n;++i)
    {
        while(hd<tl&&Slope(que[hd],que[hd+1])<mas[i].x) hd++;
        dp[i]=dp[que[hd]]+gt(que[hd],i)+mas[i].c;
        while(hd<tl&&Slope(que[tl-1],que[tl])>Slope(que[tl],i)) tl--;
        que[++tl]=i;
    }
    ll pos=n;
    while(mas[pos].p==0) pos--;
    ll ans=inf;
    for(int i=pos;i<=n;++i) ans=min(ans,dp[i]);
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

PS:此题有其它坑点，读者自己小心~

[USACO08MAR] Land Acquisition G

大意：

将$n$块土地分组，每组的价格是这组土地中最大的长宽乘积，问买下所有土地的最小花费。

思路：

个人感觉一开始的思路还是有点妙的

不妨按照长升序排序，如果长相同就宽升序

从前往后遍历的时候，考虑$i<j$，显然如果$i,j$放一组，长一定是取$j$的，那么如果$j$的宽也大于$i$的话，那么$i$就没有任何贡献。所以我们可以用一个栈来维护，把没用的东西踢掉。显然在最优决策下，每一组的土地会是连续的一段

考虑$dp_i$表示排序弹出处理之后前i个土地的最小值：

$dp_i=min_{j\leq i}\{dp_j+b_{j+1}a_i\}$,其中$a$表示长，$b$表示宽

这里$b_j$在处理之后是降序的，我们可以转化成$dp_i=min_{j\leq i}\{dp_j-b'_{j+1}a_i\},b'_j=-b_j$

考虑$x<y$,且y优于x

$-b'_ya_i+dp_j\leq -b'_xa_i+dp_x$

$\frac{dp_x-dp_y}{b'_x-b'_y}\leq a_i$，还是维护一个下凸包，并且斜率$a_i$是单增的，所以也是直接套板子

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll N=1e6+10;
const ll inf=1e18;
struct ty
{
    ll a,b;
    bool operator <(const ty & B) const
    {
        if(a==B.a) return b<B.b;
        return a<B.a;
    }
}mas[N];
ll n;
ll que[N];
ll dp[N];
ty st[N];
ll top=0;
double Slope(ll x,ll y)
{
    if(st[x+1].b==st[y+1].b) return inf;
    return 1.0*((dp[y]-dp[x])/(-st[y+1].b+st[x+1].b));
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>mas[i].a>>mas[i].b;
    }
    sort(mas+1,mas+1+n);
    for(int i=1;i<=n;++i)
    {
        while(top)
        {
            if(mas[i].b>=st[top].b) top--;
            else break;
        }
        st[++top]=mas[i];
    }
    ll hd=1,tl=0;
    que[++tl]=0;
    for(int i=1;i<=top;++i)
    {
        while(hd<tl&&Slope(que[hd],que[hd+1])<st[i].a) hd++;
        // cout<<i<<" "<<que[hd]<<endl;
        dp[i]=dp[que[hd]]+st[que[hd]+1].b*st[i].a;
        while(hd<tl&&Slope(que[tl-1],que[tl])>Slope(que[tl],i)) tl--;
        que[++tl]=i;
    }
    cout<<dp[top]<<endl;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

[ZJOI2007]仓库建设

大意：

~~本人太懒。。。~~

思路：

这题就是需要cdq分治的题了

考虑$f_i$表示第i天能够获得的最大钱数，$g_i$表示第i天最多能买多少张B券

则$\large g_i=\frac{f_i}{r_ia_i+b_i}$

故$f_i=max\{max_{j\leq i-1}\{g_j\frac{b_i}{a_i}+r_jg_j\}*a_i,f_{i-1}\}$

外层的max我们可以直接特判，内层的max就是一个典型的斜率优化dp了。

考虑$g_x<g_y$,且y优于x（这里$g$不是单调的，我们不能直接假设$x<y$）,l令$F_j=r_jg_j$

$g_x\frac{b_i}{a_i}+F_x\geq g_y\frac{b_i}{a_i}+F_y$

即$\large \frac{F_x-F_y}{g_x-g_y}\leq -\frac{b_i}{a_i}$

实际还是一个下凸包。这里横坐标是$g_j$,纵坐标是$F_j$,斜率是$-\frac{b_i}{a_i}$

横坐标不是单调的，斜率也不是单调的，看起来不是能用普通凸包来维护的样子。所以我们可以使用cdq分治

想要用单调队列维护凸包的话，我们实际上有三维偏序：

对于每一个i，它的决策点是$\{j|j<i\}$，也就是id较小的点才可以更新id较大的点
维护凸包的时候，如果x先于y加入凸包，要满足$g_x<g_y$
凸包查询最优决策点的时候，如果x先于y查询，要满足$K(x)<K(y)$，因为我们要利用决策点不降的性质来加速选择最优点的过程

显然，三维偏序正是cdq分治的拿手好戏~

第一关键字：首先将点按照斜率升序排序，能够保证查询的斜率递增，从而能用单调队列维护
第二关键字：分治时按照id分成左右两个部分。这样保证最后递归到叶子节点的时候是符合原本顺序的，且斜率查询的时候保证都是维护的点的id都是在自己之前的（其实就是一个归并排序）
第三关键字：x 每次分治结束之后内部不再有贡献，所以我们可以直接按照横坐标升序排序方便后面维护凸包

我们会发现这样处理之后就能够实现三维偏序了。

cdq分治的灵魂是用前半部分的信息来统计对后半部分的贡献，当一段区间分治结束之后，这段区间内的信息就全部处理完了，换句话说，区间内部的点之间是不会再产生贡献了，因此我们才可以随意更改该区间内部的点的顺序。将其按照横坐标排序，我们才能进行凸包的维护。同时，以横坐标为关键字的排序我们可以直接sort，但是也可以采用归并排序

最后，求出$f_i$之后，再与$f_{i-1}取max$，并更新$g_i$

具体流程：

if(l==r) 更新，退出
按照id分成左右两部分$[l,mid],(mid,r]$
cdq(l,mid)
此时$[l,mid]$已经处理好了，所以用单调队列对$[l,mid]$建凸包
$(mid,r]$区间此时是以$\frac{-b_i}{a_i}$升序,所以按顺序更新即可，并更新凸包
cdq(mid+1,r)
按照横坐标对$[l,r]$进行归并，因为该区间内部不会再有互相的贡献了

#include <bits/stdc++.h>
#define pii pair<int,int>
#define il inline
#define ll long long
#define double long double
const double eps =1e-8;
using namespace std;
const int N=1e5+10;
const ll inf=1e17;
ll n;
double s;
double A[N],B[N],R[N];
double f[N],X[N];
struct ty
{
    ll id;
    double slope;
    double a,b,k;
    //第一关键字：斜率 按照斜率升序能够保证查询的斜率递增，从而能用单调队列维护
    //第二关键字：id 分治时按照id分成左右两个部分。这样保证最后递归到叶子节点的时候是符合原本顺序的
    //且斜率查询的时候保证都是维护的点的id都是在自己之前的
    //第三关键字：x 每次分治结束之后内部不再有贡献，则按照x升序排方便后面维护凸包
    bool operator <(const ty & b) const
    {
        if(slope==b.slope) return id<b.id;
        return slope>b.slope;//斜率递减
    }
}mas[N],tmp[N];
ll que[N];
double Slope(ll x,ll y)
{
    if(X[mas[x].id]==X[mas[y].id])
    {
        return inf;
    }
    return (X[mas[y].id]*mas[y].k-X[mas[x].id]*mas[x].k)/(X[mas[y].id]-X[mas[x].id]);
}

void upd(int id,double val)
{
    if(f[mas[id].id]<val)
    {
        f[mas[id].id]=val;
        X[mas[id].id]=f[mas[id].id]/(mas[id].k*mas[id].a+mas[id].b);
    }
}
void cdq(ll l,ll r)
{
    if(l==r)
    {
        f[mas[l].id] = max(f[mas[l].id],f[mas[l].id-1]);//这里的f_{i-1}是所有排序前的i-1，所以要稍微绕一下，注意别弄错
        X[mas[l].id]=f[mas[l].id]/(mas[l].k*mas[l].a+mas[l].b);
        return;
    }
    ll mid=(l+r)>>1;
    ll posl=l,posr=mid+1;
    for(int i=l;i<=r;++i)
    {
        if(mas[i].id<=mid) tmp[posl++]=mas[i];
        else tmp[posr++]=mas[i];
    }
    for(int i=l;i<=r;++i) mas[i]=tmp[i];
    //按照id处理好了
    cdq(l,mid);
    //先处理前一个部分，保证此时前半部分的x是升序的
    ll hd=1,tl=0;
    for(int i=l;i<=mid;++i)//维护凸包
    {
        while(tl>hd&&Slope(que[tl-1],que[tl])<Slope(que[tl],i)+eps) tl--;
        que[++tl]=i;
    }
    ll id;
    for(int i=mid+1;i<=r;++i)//计算两边产生的贡献
    {
        while(tl>hd&&Slope(que[hd],que[hd+1])>mas[i].slope) hd++;
        upd(i,X[mas[que[hd]].id]*(mas[que[hd]].k-mas[i].slope)*mas[i].a);
    }
    cdq(mid+1,r);

    posl=l,posr=mid+1;
    ll tot=l-1;
    while(posl<=mid&&posr<=r)
    {
        if(X[mas[posl].id]<X[mas[posr].id]) tmp[++tot]=mas[posl++];
        else tmp[++tot]=mas[posr++];
    }
    while(posl<=mid) tmp[++tot]=mas[posl++];
    while(posr<=r) tmp[++tot]=mas[posr++];
    for(int i=l;i<=r;++i) mas[i]=tmp[i];
}
void solve()
{
    cin>>n>>s;
    for(int i=1;i<=n;++i)
    {
        cin>>A[i]>>B[i]>>R[i];
        mas[i].id=i;
        mas[i].a=A[i];mas[i].b=B[i];mas[i].k=R[i];
        mas[i].slope=-B[i]/A[i];
        // if(i>1) continue;
        X[mas[i].id]=s/(R[i]*A[i]+B[i]);
        // mas[i].y=R[i]*mas[i].x;
    }
    for(int i=1;i<=n;++i) f[i]=s;
    sort(mas+1,mas+1+n);
    cdq(1,n);
    cout<<fixed<<setprecision(4)<<f[n]<<endl;
}
int main()
{
    // freopen("1.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

后记

斜率优化dp在大部分情况下都是结合决策单调性进行的（大部分），所以也比较套路

另外还有结合Wqs二分来处理前n个数限定分m段的情况等的套路，个人感觉决策单调性优化的水还是有点深的，有空会试试写一期总结

加油~

动态规划

#学习笔记 #动态规划 #算法

斜率优化dp总结

https://sophilex.github.io/斜率优化dp总结/

作者

Sophilex

发布于

2023年12月19日

许可协议

各类基于决策单调性的dp优化上一篇

群作用下一篇