斜率优化dp总结

_zjz · 2018-11-22 21:36:54 · 个人记录

首先以玩具装箱为例:

题目链接:玩具装箱

设{f[i]}为到前i个玩具的最小价值

易得:{f[i]=min(f[i],f[j]+(a[i]-b[j])^2)}

其中{a[i]=sum[i]+i,b[i]=sum[i]+i+l+1};

但时间复杂度为O(n^2),需要优化;

将上式展开,得:

{f[i]=f[j]+a[i]^2-2*a[i]*b[j]+b[j]^2}

可以将{2*a[i]} 看为斜率,{(b[j],f[j]+b[j]^2)} 看成平面直角坐标系上的点

因此就把上述该式转为形如y=kx+b的式子

我们要让f[i]最小, 所以就要找一个合法的j,使得该直线在y轴上的截距最小

当枚举到i点时,最优的点组成了一个下凸包

显然,凸包中相邻两点的斜率单调递增,

目标直线2*a[i]也是单调递增

根据线性规划知识易知,满足最优pj的点一定是第一个第一个slope(Pj,Pj+1)>2*a[i]的点

因为加入slope(Pj,Pj+1) <= 2*a[i],我们可以通过将Pj移动到Pj+1来让答案更优

那么如何维护凸包???

单调队列:

1.while(head < tail && slope(q[head],q[head + 1]) < 2 *a(i))++ head;
2.f[i] = f[q[head]] + (a(i) - b(q[head])) * (a(i) - b(q[head]));
3.while(head < tail && slope(i,q[tail - 1]) < slope(q[tail - 1],q[tail])) -- tail;
4.q[++ tail] = i;

解释:

若slope(Pj,Pj+1)<2*a[i],显然Pj不是最优直接删掉

因为目标直线斜率单调递增，所以当前删去的Pj 一定对之后的dp[i]也不是最优，不会造成影响

而操作3的理由如下：

显然，满足操作3的要求时，P_tail凸包内部，一定不是最优，因此可以删去

以上也就是斜率优化的基本思想.

放上该题的代码:

#include<bits/stdc++.h>
#define int long long

using namespace std;

inline int read()
{
    int X = 0,w = 0;char ch = 0;
    while(!isdigit(ch)){w |= ch == '-';ch = getchar();}
    while(isdigit(ch)){X = X * 10 + ch - '0';ch = getchar();}
    return w ? -X:X;
}

const int N = 5e5 + 101;
int f[N], sum[N];
int n, l, q[N];

double a(int x){return sum[x] + x;}
double b(int x){return sum[x] + x + l + 1;}
double X(int x){return b(x);}
double Y(int x){return f[x] + b(x) * b(x);}
double slope(int i,int j){return (Y(i) - Y(j)) / (X(i) - X(j));}

signed main()
{
    n = read();l = read();
    for(int i = 1;i <= n;i ++)
    scanf("%lld",&sum[i]),sum[i] += sum[i - 1];
    int head = 1, tail = 1;
    for(int i = 1;i <= n;i ++)
    {
        while(head < tail && slope(q[head],q[head + 1]) < 2 * a(i)) ++ head;
        f[i] = f[q[head]] + (a(i) - b(q[head])) * (a(i) - b(q[head]));
        while(head < tail && slope(i,q[tail - 1]) < slope(q[tail - 1],q[tail])) -- tail;
        q[++ tail] = i;
    }
    cout << f[n];
}

一些例题:

1.APIO特别行动队:

原题链接:特别行动队

我们设{f[i]}为到i的最大价值;

易得,{f[i]=min(f[j]+a*x*x+b*x+c,f[i])};

其中x为{sum[i]-sum[j]}

考虑斜率优化:

我们将上述dp方程展开就可已得到:

{(2*sum[i]+b)*sum[j]+???=f[j]+a*sum[j]^2}

具体怎么推导就不细说了:

将{2*sum[i]+b}看作斜率,{(sum[i],f[i]+a*sum[j]^2)}看为点

维护一个下凸包即可,具体的直接套板子就行

详见代码:

#include<bits/stdc++.h>
#define int long long

using namespace std;

inline int read()
{
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch)){X=X*10+ch-'0';ch=getchar();}
    return w?-X:X;
}

const int N=2e6+101;
int n,a,b,c;
int val[N],f[N],sum[N],q[N];

template<typename T>T Max(T a,T b){return a>b?a:b;}

double X(int i){return sum[i];}
double Y(int i){return f[i]+a*sum[i]*sum[i];}
double slope(int i,int j){return (Y(j)-Y(i))/(X(j)-X(i));}
int Val(int x){return a*x*x+b*x+c;}

signed main()
{
    n=read();a=read();b=read();c=read();
    for(int i=1;i<=n;i++)val[i]=read();
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+val[i];
    int head=1,tail=1;
    for(int i=1;i<=n;i++)
    {
        while(head<tail&&slope(q[head],q[head+1])>2*a*sum[i]+b)++head;
        f[i]=f[q[head]]+Val(sum[i]-sum[q[head]]);
        while(head<tail&&slope(i,q[tail-1])>slope(q[tail-1],q[tail]))--tail;
        q[++tail]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}

2.ZJOI仓库建设:

题目链接:仓库建设

我们设{f[i]}为到i点的最小价值

易得到:

{f[i]=min(f[i],f[j]+x[i]*(sum1[i]-sum1[j])-(sum2[i]-sum2[j]+c[i])}

其中,{sum1[i]}为1到i的{p[i]}前缀和

将上式转化,得: ${x[i]*sum1[j]+???=f[i]+sum2[i]}

依旧套上面的板子即可:

详见代码:

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline int read()
{
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch)){X=X*10+ch-'0';ch=getchar();}
    return w?-X:X;
}

const int N=1e6+101;
ll x[N],p[N],c[N],sum1[N],sum2[N],f[N],q[N];
int n;

double X(int i){return sum1[i];}
double Y(int i){return f[i]+sum2[i];}
double slope(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));}

ll Val(int l,int r)
{
    return x[r]*(sum1[r]-sum1[l-1])-sum2[r]+sum2[l-1]+c[r];
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++){
        x[i]=read();p[i]=read();c[i]=read();
    }
    for(int i=1;i<=n;i++){
        sum1[i]=sum1[i-1]+p[i];sum2[i]=sum2[i-1]+p[i]*x[i];
    }
    int head=1,tail=1;
    for(int i=1;i<=n;i++)
    {
        while(head<tail&&slope(q[head],q[head+1])<x[i])++head;
        f[i]=f[q[head]]+Val(q[head]+1,i);
        while(head<tail&&slope(q[tail],q[tail-1])>slope(q[tail],i))--tail;
        q[++tail]=i;
    }
    cout<<f[n];
}

3.征途

征途

首先直接求方差显然不好求,

于是可以先化简方差的式子

设分的每一段和为x

所以:

{s^2=m^2*(1/m)*((x_1-x)^2+......(x_m-x)^2)}

于是:

{s^2=m*(x_1^2-2*x_1*x+x^2+.......x_m-2*x_m*x+x^2)}

将m乘进去:

{s^2=m*(x_1^2+.......+x_m^2)-2*m*x*sum+sum^2}

其中{sum}为{1-n}的总和

这样我们只需让分的每一段的和的平方的总和最小即可;

答案即为f[m][n]*m-sum[n]*sum[n];

直接dp是{O(n^2m)}需要优化

考虑斜率优化:

在枚举{f[j][i]}最优何时取到可以斜率优化;

因此:设z=j-1

所以:

f[j][i]=f[z][k]+(sum[i]-sum[k])^2

展开:

2*sum[i]*sum[k]+???=f[z][k]+sum[k]^2

把2*sum[i]看为斜率,(sum[k],f[z][k]+sum[k]^2)

看成一个点

每次枚举j时直接{O(n)}的维护下凸包即可;

其他的就是套斜率优化的板子即可;

#include<bits/stdc++.h>
#define int long long

using namespace std;

inline int read()
{
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch)){X=X*10+ch-'0';ch=getchar();}
    return w?-X:X;
}
//f[i]=min(f[i],f[j]+(sum[i]-sum[j])^2;
const int N=4005;
int f[N][N],sum[N],q[N],z,n,m;
double X(int i){return sum[i];}
double Y(int i){return f[z][i]+sum[i]*sum[i];}
double slope(int i,int j){return (Y(j)-Y(i))/(X(j)-X(i));}
int pi(int x){return x*x;}

signed main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
    sum[i]=read(),sum[i]+=sum[i-1];
    f[0][0]=0;
    for(int i=1;i<=n;i++)f[1][i]=sum[i]*sum[i];
    for(int j=2;j<=m;j++)
    {
        int head=1,tail=1;
        z=j-1;
        memset(q,0,sizeof(q));
        for(int i=1;i<=n;i++)
        {
            while(head<tail&&slope(q[head],q[head+1])<2*sum[i])++head;
            f[j][i]=f[z][q[head]]+pi(sum[i]-sum[q[head]]);
            while(head<tail&&slope(q[tail],q[tail-1])>slope(q[tail-1],i))--tail;
            q[++tail]=i;
        }
    }
    cout<<f[m][n]*m-sum[n]*sum[n];
}

4.土地购买

土地购买

这题好像无法直接dp;

没关系,我们转化一下即可

首先我们需要由题意知道:

假如一个矩形被另一个矩形所嵌套

则这个矩形对答案一定没有贡献;

我们首先将这些矩形中没有用的全部删去

将x为第一关键字从小到大排序,y为第二关键字从大到小排序;

于是我们得到的序列一定是x单增,y单减的序列

于是得到方程f[i]=min(f[i],f[j]+x[i]*y[j+1]);

套斜率优化即可,

具体怎么优化就不再赘述了.

放上本题代码:

#include<bits/stdc++.h>
#define int long long

using namespace std;

inline int read()
{
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch)){X=X*10+ch-'0';ch=getchar();}
    return w?-X:X;
}

const int N=2e6+101;
struct node{
    int x,y,flag;
    bool operator < (const node &a)const{
         return x==a.x?y<a.y:x<a.x;
    }
}b[N],c[N];
int n,cnt,q[N],f[N],e[N],maxn;

bool cmp(node a,node b){return a.x==b.x?a.y>b.y:a.x<b.x;}
double X(int i){return -c[i+1].y;}
double Y(int i){return f[i];}
double slope(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));}
#define lowbit(i) i&-i
void update(int x)
{
    ++x;
    for(int i=x;i<=maxn+1;i+=lowbit(i))
    e[i]++;
}
int query(int x)
{
    int sum=0;++x;
    for(int i=x;i;i-=lowbit(i))
    sum+=e[i];
    return sum;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    b[i].x=read(),b[i].y=read(),maxn=max(maxn,b[i].y);
    sort(b+1,b+n+1);
    for(int i=n;i>=1;i--)
    {
        if((n-i)-query(b[i].y-1)>0)b[i].flag=1;
        update(b[i].y);
    }
    for(int i=1;i<=n;i++)
    if(!b[i].flag)c[++cnt]=b[i];
    int head=1,tail=1;
    for(int i=1;i<=cnt;i++)
    {
        while(head<tail&&slope(q[head],q[head+1])<c[i].x)++head;
        f[i]=f[q[head]]+c[i].x*c[q[head]+1].y;
        while(head<tail&&slope(q[tail],q[tail-1])>slope(q[tail-1],i))--tail;
        q[++tail]=i;
    }
    cout<<f[cnt];
}

小结:

1.斜率优化的数的方式是比较好理解的，我们每次找到动态规划的状态转移方程后就可以直接转换

2.斜率优化只适用于具有单调性的转移方程，即最后简化后的等式左右中的一方必定有一个是给定单调的函数，譬如前缀和。

3.每次斜率优化都要设更优解的自变量，然后用更优解来维护斜率

4.保证储存斜率的队列单调

5.很值得注意到一点，对于初学者而言我们可能会想，为什么可以把斜率转换成这样的形式，其实不然，斜率的形式并不唯一，我们不需要去刻意仿照别人的斜率等式，只要二者等价，即都可以求出正解

6.注意正负，可以看见斜率的会有除法运算，记得不等式除负数时要变号（可能就我这么傻，不会变号），不然公式推错那就GG了

7.最后就是要在做题中理解斜率优化的妙用，可以参考一下他人的代码，或许会大有启发。

8.斜率优化关键在于式子的推导,只要推导正确其他就是板子了