斜率优化

2023-06-15

OI 知识>动态规划

3.6k words

斜率优化

斜率优化的核心在于推导状态转移方程使之变为斜率一定的一次函数，使 \(f[i]\) 与截距相关，将求 \(f[i]\) 最值转化为用一条定斜率的直线去过平面上的点，使截距取到最值。

一，引入

1D 动态规划模型

1D 动态规划模型是 DP 中一类非常基本、非常重要的模型，所求的是最优化问题，1D 动态规划可大致归纳为如下形式

\(F[i]=\) \(min_{L(i)\leq j\leq R(i)}\) \((F[j]+\) \(val(i,j))\)

接下来对这一通式进行解读。\(F[i]\) 和 \(F[j]\) 代表 DP 数组，\(L(i)\) 和 \(R(i)\) 是关于变量 \(i\) 的一次函数，用于划定 \(j\) 的上下界，\(val(i,j)\) 为一个关于变量 \(i\) 和变量 \(j\) 的多项式函数，也是 DP 优化的关键所在。

状态转移中的斜率

对于一个 1D 动态规划问题，列出其状态转移，发现 \(val(i,j)\) 中包含 \(i\) 与 \(j\) 的乘积项。最简单的形如

\(F[i]=\) \(F[j]+\) \(b_ib_j\) \(\Longleftrightarrow\) \(F[j]=\) \(-b_ib_j+\) \(F[i]\)

发现 \(F[j]\) 的表达形如 \(F[j]=kb_j+b\)，为一个一次函数，斜率为 \(-b_i\)。与直线 \(b_j=0\) 的截距即为 \(F[i]\)。斜率优化将动态规划转化为数学中的线性规划问题。下文将详细讲解。

二，思路

例题：任务安排

有 \(N\) 个有序任务，第 \(i\) 个任务耗时 \(T_i\)，费用系数 \(C_i\)，将任务分组顺序执行，执行每组前需要 \(S\) 的启动时间，一组中的所有任务将顺序执行，每个任务的完成时刻是其所在组全部任务的完成时刻，每个任务的花费是完成时刻乘费用系数。求最小总费用。

对于 \(T\) 和 \(C\)，可以求出前缀和数组 \(sumT,sumC\)，\(F[i][j]\) 表示将前 \(i\) 个任务分成 \(j\) 批执行的最小费用，第 \(j\) 批任务的完成时刻是 \(j\times S+sumT[i]\)，状态转移方程如下：

\(F[i][j]=\) \(min_{0\leq k<i}\) \((F[k][j-1]+\) \((S\times\) \(j+\) \(sumT[i])\times\) \((sumC[i]-\) \(sumC[k]))\)

直接 DP，复杂度为 \(O(N^3)\)，考虑优化。

优化一：费用提前计算

在刚才的状态转移方程中，我们需要 \(j\) 仅仅是为了判断启动了多少次，发现如果没有 \(j\)，不易得启动了多少次，但可以知道每次启动时间 \(S\) 都会累加到此后所有任务的完成时刻中，于是 DP 数组可以维度压缩，设 \(F[i]\) 表示把前 \(i\) 个元素分若干批完成的最小费用，则：

\(F[i]=\) \(min_{0\leq j<i}\) \((F[j]+\) \(sumT[i]\times\) \((sumC[i]-\) \(sumC[j])+\) \(S\times\) \((sumC[N]-\) \(sumC[j]))\)

发现在这一转移方程中，我们把之后的费用提前累加到了答案中，这种“费用提前计算”是一种经典思想。于是时间复杂度可以降至 \(O(N^2)\)。

code

long long f[5005],sumt[5005],sumc[5005];
int n,s;
int main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        int t,c;
        cin>>t>>c;
        sumt[i]=sumt[i-1]+t;
        sumc[i]=sumc[i-1]+c;
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            f[i]=min(f[i],f[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[i]));
    cout<<f[n]<<endl;
    return 0;
}

优化二：斜率优化

在费用提前计算的基础上进一步优化，对状态转移方程变形得：

\(F[i]=\) \(min_{0\leq j<i}\) \((F[j]-\) \(sumC[j]\times\) \((sumT[i]+\) \(S)+\) \(sumT[i]\times\) \(sumC[i]+\) \(S\times\) \(sumC[N]))\)

把 \(min\) 函数去掉，将关于 \(j\) 的值 \(F[j]\) 和 \(sumC[j]\) 看作变量，其余部分作为常量，得到

\(F[j]=\) \((sumT[i]+\) \(S)\times\) \(sumC[j]+\) \(F[i]-\) \(sumT[i]\times\) \(sumC[i]-\) \(S\times\) \(sumC[N]\)

在以 \(sumC[j]\) 为横坐标，\(F[j]\) 为纵坐标的平面直角坐标系中，这是一条以 \((sumT[i]+\) \(S)\) 为斜率，以 \(F[i]-\) \(sumT[i]\times\) \(sumC[i]-\) \(S\times\) \(sumC[N]\) 为截距的直线。其中斜率为已知量，截距中除 \(F[i]\) 外均为已知量。则候选决策为坐标中的点集，每个 \(j\) 对应一个 \((sumC[j],F[j])\)，而每个 \(F[i]\) 也都对应了一个截距，当截距最小时 \(F[i]\) 取到最小值。

于是 DP 问题就被转化为了这样一个线性规划问题

示例

用一条斜率已知的直线去过平面直角坐标系内的点，使截距最小，发现若这条斜线从下向上平移，接触到第一个点时截距最小。通过推导公式或画图直观感受，我们会发现第一个被斜线接触的点有特殊性质，假设该点为 \(j_2\)，该点左侧有 \(j_1\)，右侧有 \(j_3\)，则

\(\frac{F[j_2]-F[j_1]}{sumC[j_2]-sumC[j_1]}<\) \(\frac{F[j_3]-F[j_2]}{sumC[j_3]-sumC[j_2]}\)

发现这两个式子恰好斜率，于是我们可以想到要维护一个下凸壳，使所有点包含在这个凸壳内，令直线截距最小的点一定在这个下凸壳上，且两侧斜率一侧大于直线斜率，一侧小于直线斜率。

接下来只要解决如何维护这个凸壳即可。发现对于凸壳，其斜率单调变化，于是可以建立单调队列来维护，每插入一个点时，将队尾不符合单调性的点弹出，使之被包在凸壳内。

在本题我们发现斜率 \(S+sumT[i]\) 单调递增，所以可以每次把队头斜率小于此的弹出，然后取队头即可，若斜率不满足单调递增，则答案不一定在队头，在队列中二分查找即可。

整个算法时间复杂度为 \(O(N)\)。

code

int main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        int t,c;
        cin>>t>>c;
        T[i]=T[i-1]+t,C[i]=C[i-1]+c;
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0,q[1]=0;;
    int l=1,r=1;
    for(int i=1;i<=n;i++)
    {
        while(l<r&&(f[q[l+1]]-f[q[l]])<=(s+T[i])*(C[q[l+1]]-C[q[l]]))
            l++;
        f[i]=f[q[l]]-C[q[l]]*(s+T[i])+T[i]*C[i]+s*C[i];
        while(l<r&&(f[q[r]]-f[q[r-1]])*(C[i]-C[q[r]])>=(f[i]-f[q[r]])*(C[q[r]]-C[q[r-1]]))
            r--;
        q[++r]=i;
    }
    cout<<f[n]<<endl;
    return 0;
}

三，总结

概述斜率优化的算法：

将初始状态入队；
每次使用一条和 \(i\) 相关的直线 \(f[i]\) 取切维护的凸壳，找到最优策略，更新 \(dp_i\)；
保证单调性地加入状态 \(dp_i\)。

斜率优化题目的主要难点在于状态转移方程的推导变形，以及对单调性的判断。

四，习题

洛谷P3195 玩具装箱

\(O(n)\) 做法：设 \(f[i]\) 表示前 \(i\) 个物品被分为若干组，列出状态转移方程：\(f[i]=\) \(min_{0\leq j<i}(f[j]+\) \((sum[i]-\) \(sum[j]+\) \(i-\) \(j-\) \(l-\) \(1)^2)\)，去掉 \(min\) 函数得：\(f[i]=\) \(f[j]+\) \(((sum[i]+\) \(i-\) \(l-\) \(1)-\) \((sum[j]-\) \(j))^2\)。设 \(a_i=\) \(sum[i]+\) \(i-\) \(l-\) \(1\)，设 \(a_j=\) \(sum[j]-\) \(j\)，则有：\(f[i]=\) \(f[j]+\) \((a_i-\) \(a_j)^2=\) \(f[j]+\) \(a_i^2+\) \(a_j^2+\) \(2a_ia_j\)，移项，得到：\(f[j]+a_j^2=-2a_ia_j-a_i^2+f[i]\)，可用斜率优化，套用斜率优化模板即可。

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,s,q[50005];
ll c[50005],f[50005];
ll y(int x) {return f[x]+c[x]*c[x];}
ll k(int x) {return 2*(c[x]-s);}
ll d(int x) {return (c[x]-s)*(c[x]-s);}
inline ll rd()
{
    ll x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void wt(ll x)
{
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
signed main()
{
    n=rd(),s=rd(),s++;
    for(int i=1;i<=n;i++) c[i]=rd(),c[i]+=c[i-1]+1;
    int l=1,r=1;
    for(int i=1;i<=n;i++)                                
    {
        while(l<r&&y(q[l+1])-y(q[l])<=(c[q[l+1]]-c[q[l]])*k(i)) l++;
        f[i]=y(q[l])-k(i)*c[q[l]]+d(i);
        while(l<r&&(y(q[r])-y(q[r-1]))*(c[i]-c[q[r]])>=(y(i)-y(q[r]))*(c[q[r]]-c[q[r-1]])) r--;
        q[++r]=i;
    }
    return wt(f[n]),0;
}

洛谷P3628 特别行动队

\(O(n)\) 做法：设 \(f[i]\) 表示前 \(i\) 个士兵被分为若干组，列出状态转移方程：\(f[i]=\) \(min_{0\leq j<i}(f[j]+\) \(a(sum[i]-\) \(sum[j])^2+\) \(b(sum[i]-\) \(sum[j])+\) \(c)\)，去掉 \(min\) 函数得：\(f[i]=\) \(f[j]+\) \(a(sum[i]-\) \(sum[j])^2+\) \(bsum[i]-\) \(bsum[j]+\) \(c\)，开方得：\(f[i]=\) \(f[j]+\) \(asum[i]^2+\) \(asum[j]^2-\) \(2asum[i]sum[j]+\) \(bsum[i]-\) \(bsum[j]+\) \(c\)，移项，得到：\(f[j]+\) \(asum[j]^2-\) \(bsum[j]=\) \(2asum[i]sum[j]+\) \(f[i]-\) \(asum[i]^2-\) \(bsum[i]-\) \(c\)，可用斜率优化，套用斜率优化模板即可，需要注意 \(sum[j]\) 的系数 \(2asum[i]<0\)，斜率是单调递减的，所以凸壳斜率的单调性与此前相反。

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a,b,c,s[1000005],f[1000005],q[1000005];
ll y(ll x) {return f[x]+a*s[x]*s[x]-b*s[x];}
ll k(ll x) {return 2*a*s[x];}
ll d(ll x) {return a*x*x+b*x+c;}
inline ll rd()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void wt(ll x)
{
    if(x<0) {putchar('-'),wt(-x);return;}
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
signed main()
{
    n=rd(),a=rd(),b=rd(),c=rd();
    for(int i=1;i<=n;i++) s[i]=rd(),s[i]+=s[i-1];
    int l=1,r=1;
    for(int i=1;i<=n;i++)
    {
        while(l<r&&y(q[l+1])-y(q[l])>=(s[q[l+1]]-s[q[l]])*k(i)) l++;
        f[i]=f[q[l]]+d(s[i]-s[q[l]]);
        while(l<r&&(y(q[r])-y(q[r-1]))*(s[i]-s[q[r]])<=(y(i)-y(q[r]))*(s[q[r]]-s[q[r-1]])) r--;
        q[++r]=i;
    }
    return wt(f[n]),0;
}

洛谷P2900 Land Acquisition G

\(O(n)\) 做法：设 \(f[i]\) 表示前 \(i\) 块地被分为若干组，列出状态转移方程：\(f[i]=\) \(min_{0\leq j<i}(f[j]+\) \(max_{j<k\leq i}w[k]\times\) \(max_{j<k\leq i}l[k])\)，发现在 \(min\) 函数中还有 \(max\) 函数，不容易优化，考虑先对这些土地排序，以长度为第一关键字递增，宽度为第二关键字递减排序，排序过程中发现如果一块地的长度和宽度都比另一块地小，则它可以被包含于另一块地的费用中，之后不需要再考虑该块地，所以在排序过程中还需要将这种“可以被包含”的地块删去。最后剩下的地块类似于下图：

排序后，发现对于一个地块，如果排名在它前后的地块被分到了同一组，那么这一地块可以被分到该组而不产生贡献，如下图：

所以如果选中了两个不相邻的地块，把它们之间的地块也选入是更优解，从而最优的分组应该是若干连续段，得到新的状态转移方程：\(f[i]=\) \(min_{0\leq j<i}(f[j]+l[j+1]\times\) \(w[i])\)，去掉 \(min\) 函数，移项，得到：\(f[j]=\) \(-w[i]l[j+1]+\) \(f[i]\)，这里需要注意新的分组是从 \(j+1\) 到 \(i\) 的。之后套用斜率优化即可。这里排序的时间复杂度是 \(O(\log n)\) 的，去重是 \(O(n)\) 的，DP 是 \(O(n)\) 的，总复杂度近似为 \(O(n)\)。

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,f[50005],q[50005];
struct node
{
    ll W,L;
    bool operator < (const node &x) const
    {return W==x.W?L>x.L:W<x.W;}
}land[50005];
ll w[50005],l[50005];
inline ll rd()
{
    ll x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
signed main()
{
    n=rd();
    for(ll i=1;i<=n;i++) land[i].W=rd(),land[i].L=rd();
    sort(land+1,land+n+1);
    ll h=1,t=0;
    for(ll i=1;i<=n;i++)
    {
        while(h<=t&&land[q[t]].L<=land[i].L) t--;
        q[++t]=i;
    }
    for(ll i=1;i<=t;i++) w[i]=land[q[i]].W,l[i]=land[q[i]].L;
    n=t,h=1,t=1,q[1]=0;
    for(ll i=1;i<=n;i++)
    {
        while(h<t&&f[q[h+1]]-f[q[h]]<=(l[q[h]+1]-l[q[h+1]+1])*w[i]) h++;
        f[i]=f[q[h]]+l[q[h]+1]*w[i];
        while(h<t&&(f[q[t]]-f[q[t-1]])*(l[q[t]+1]-l[i+1])>=(l[q[t-1]+1]-l[q[t]+1])*(f[i]-f[q[t]])) t--;
        q[++t]=i;
    }
    cout<<f[n]<<endl;
    return 0;
}

洛谷P4360 锯木厂选址

\(O(n)\) 做法：修建两个锯木厂，将山坡划分为了三段，锯木厂直接修建在某棵树所在的位置显然比修建在该棵树与下一棵之间更优，设 \(d[i]\) 表示在第 \(i\) 棵树所在地修建锯木厂省下的距离，即第 \(i\) 棵树到山脚的距离，\(w[i]\) 表示在前 \(i\) 棵树的重量和，则在第 \(i\) 棵树所在地建锯木厂可省下花费 \(d[i]\times w[i]\)，于是得到第一个（距离山顶最近）的锯木厂修在 \(i\)，第二个锯木厂修建在 \(j\) 的最小花费为 \(ans=min(sum-\) \(d[j]w[j]-\) \(d[i](w[i] -\) \(w[j]))\)。去掉 \(min\) 函数，移项，得到：\(d[j]w[j]=\) \(-d[ i ]w[ j ]+\) \(sum-\) \(ans-\) \(d[i]w[i]\)，套用斜率优化。

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,sum,ans,l,r,w[20005],d[20005],q[20005];
inline ll rd()
{
    ll x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
signed main()
{
    n=rd();
    for(ll i=1;i<=n;i++)
        w[i]=rd(),d[i]=rd(),w[i]+=w[i-1],sum+=w[i]*d[i];
    for(ll i=n;i;i--) d[i]+=d[i+1];
    ans=0x3f3f3f3f,l=1,r=1,q[1]=0;
    for(ll i=1;i<=n;i++)
    {
        while(l<r&&d[q[l]]*w[q[l]]-d[q[l+1]]*w[q[l+1]]<=(w[q[l]]-w[q[l+1]])*d[i]) l++;
        ans=min(ans,sum-d[q[l]]*w[q[l]]-d[i]*(w[i]-w[q[l]]));
        while(l<r&&(d[q[r-1]]*w[q[r-1]]-d[q[r]]*w[q[r]])*(w[q[r]]-w[i])<=(w[q[r-1]]-w[q[r]])*(d[q[r]]*w[q[r]]-d[i]*w[i])) r--;
        q[++r]=i;
    }
    cout<<ans<<endl;
    return 0;
}

Categories

Tags

Archives

Recent Posts

斜率优化

斜率优化

一，引入

1D 动态规划模型

状态转移中的斜率

二，思路

优化一：费用提前计算

优化二：斜率优化

三，总结

四，习题

洛谷P3195 玩具装箱

洛谷P3628 特别行动队

洛谷P2900 Land Acquisition G

洛谷P4360 锯木厂选址