目录

前言

最近刷BZOJ的题目的时候，发现做到了很多题目都是用到了斜率优化，这个优化很早也接触过，但也没有仔细地去学。最近认真的去学了一下，就在这里做个整理

概要

斜率优化是基于单调队列或单调栈的一种优化DP的方式，当DP的决策具有单调性的时候，我们就可以通过维护单调队列或者单调栈来维护这个最优的决策，最终实现\(O(1)\)的DP转移。

知识点讲解

斜率优化如果空着讲实际上有点虚的，所以这里以这题比较基础的斜率优化DP为例。

单调性归纳证明

之前说过，在使用斜率优化之前，应该证明这个DP转移是具有决策的单调性的。首先我们先知道什么是决策单调性。决策单调性大致就是指对于\(dp[i]\)的转移，如果任意两种转移方式\(dp[j]\rightarrow dp[i]\)、\(dp[k]\rightarrow dp[i]\)，\(j<k\)并且从\(k\)转移至\(i\)要优于\(j\)，那么对于\(dp[i+1]\)的转移中，从\(k\)转移至\(i+1\)也一定优于\(j\)。

下面我们开始证明：

对于题目，我们可以先把所有的土地按\(a\)升序排序，然后对于\(b\)取出递减的一串（因为如果不是递减的话，那么就可以和别的土地一并购买，对答案并没有贡献，所以可以不用计算）。这样我们就得到了一个\(a\)递增，\(b\)递减的序列。这样我们就可以很简单的列出\(dp\)转移方程。记\(dp[i]\)为枚举到第\(i\)块土地时，最少的花费为\(dp[i]\)，\(a[i],b[i]\)分别为土地的长和宽，于是我们很容易得到转移方程：\(dp[i]=min(dp[j]+a[i]*b[j+1])\)，并且这里的\(b\)是递增的。

现在我们假设有\(j\)，\(k\)\((j<k)\)两种方式转移至\(i\)，并且\(k\)转移要优于\(j\)，所以我们可以得到：

\(dp[k]+a[i]*b[k+1]\leq dp[j]+a[i]*b[j+1]\)

然后我们假设

\(a[i+1]=a[i]+v(v\geq0)\)，那么就有：

\(dp[k]+a[i+1]*b[k+1]\leq dp[j]+a[i+1]*b[j+1]\)

\(\Longrightarrow\)

\(dp[k]+a[i]*b[k+1]+v*b[k+1]\leq dp[j]+a[i]*b[j+1]+v*b[j+1]\)

而由于排序之后我们的

\(b\)是递减的，所以

\(v*b[k+1]\geq v*b[j+1]\)，所以上面的不等式始终是成立的，这样就证明了这个决策是具有单调性的。

基于单调性的转移优化

我们将得到的决策单调性的式子展开，可以得到：

\(dp[k]+a[i]*b[k+1]\leq dp[j]+a[i]*b[j+1]\)

\(a[i]*(b[j+1]-b[k+1])\geq dp[k]-dp[j]\)

\(a[i]\geq \frac{dp[k]-dp[j]}{b[j+1]-b[k+1]}\)

于是我们记斜率为

\(slop(j,k)=\frac{dp[k]-dp[j]}{b[j+1]-b[k+1]}\)，如果这个值小于等于当前的

\(a[i]\)，就说明

\(k\)的决策比

\(j\)的优。

这样这个东西就很适合单调队列了。对于一个单调队列，我们用

\(l\)表示队首，

\(r\)表示队尾，那么每次枚举到一个

\(i\)的时候，我们就要进行两种更新了：

1.

\(slop(que[l],que[l+1])<=a[i]\)时，说明

\(que[l]\)没有

\(que[l+1]\)更优，那么可以直接将

\(que[l]\)弹出队列。

2.

\(slop(que[r],i)<=slop(que[r-1],que[r])\)时，说明

\(que[r]\)没有

\(que[r-1]\)更优，因为如果当某一时刻枚举到

\(t\)时刻，假设

\(slop(que[r-1],que[r])<=a[t]\)，那么一定有

\(slop(que[r],i)<=a[t]\)，所以

\(que[r]\)相当于是没有用的，在这里就直接可以弹出队列了。

实际上，这上面两种操作实际上就是在进行维护凸包的的操作，所以斜率优化在某种意义上也是在维护上（下）凸包。

最后我们发现在经过上述操作之后，在单调队列队首的元素就是当前的最优转移，直接利用这个进行转移即可，这样转移的复杂度就是

\(O(1)\)的，每个点都会被最多遍历到一次，所以总的复杂度为

\(O(n)\)的。

例题AC代码

/**************************************************************    Problem: 1597    User: czl2333    Language: C++    Result: Accepted    Time:168 ms    Memory:5612 kb****************************************************************/ #include 
    
     using namespace std;typedef long long ll;bool Finish_read;template
     
      inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}template
      
       inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}template
       
        inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}template
        
         inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}/*================Header Template==============*/#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);const int maxn=1e5+500;int n,tot;struct plot {    ll a,b;    bool operator < (const plot &rhs) const {        return a!=rhs.a?a
         
        
       
      
     
    

练习题

BZOJ1096 仓库建设

解题思路

很容易推出DP转移方程：

\(dp[i]=min(dp[j]+cost(i,j))+c[i]\)

重点就是怎么快速的算出

\(cost(i,j)\)。我们把

\(cost\)的计算公式写出来：

\(cost(i,j)=\sum_{k=j+1}^{i}p[k]*(x[i]-x[k])＝x[i]*\sum_{k=j+1}^{i}p[k]-\sum_{k=j+1}^{i}p[k]*x[k]\)

我们记

\(sum[i]\)为

\(p[i]\)的前缀和，

\(b[i]\)为

\(p[i]*x[i]\)的前缀和，那么DP转移就是：

\(dp[i]=min(dp[j]+x[i]*(sum[i)-sum[j])-(b[i])-b[j])+c[i]\)

于是我们就可以愉悦的用斜率优化来做这道题了，如果

\(k>j\)并且

\(k\)比

\(j\)更优，那么：

\(dp[j]+x[i]*(sum[i)-sum[j])-(b[i])-b[j]\geq dp[k]+x[i]*(sum[i)-sum[k])-(b[i])-b[k]\)

整理一下可得：

\(\frac{dp[k]−dp[j]+b[k]−b[j]}{sum[k]−sum[j]}\leq s[i]\)

AC代码

/**************************************************************    Problem: 1096    User: czl2333    Language: C++    Result: Accepted    Time:2032 ms    Memory:52100 kb****************************************************************/ #include 
    
     using namespace std;typedef long long ll;bool Finish_read;template
     
      inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}template
      
       inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}template
       
        inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}template
        
         inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}/*================Header Template==============*/#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);const int maxn=1e6+500;int n;ll dis[maxn],c[maxn],p[maxn],f[maxn],sum[maxn],b[maxn];int l,r;int que[maxn];/*==================Define Area================*/double Cal(int x,int y) {    return (double)(f[y]-f[x]+b[y]-b[x])/(double)(sum[y]-sum[x]);} int main() {    read(n);    for(int i=1;i<=n;i++) {        read(dis[i]);read(p[i]);read(c[i]);    }    for(int i=1;i<=n;i++) {        sum[i]=sum[i-1]+p[i];        b[i]=b[i-1]+p[i]*dis[i];    }    for(int i=1;i<=n;i++) {        while(l
         
          
           Cal(que[r],i)) r--; que[++r]=i; } printf("%lld\n",f[n]); return 0;}
          
         
        
       
      
     
    

BZOJ1911 特别行动队

解题思路

还是同普通的DP一样，我们记\(dp[i]\)为枚举到第\(i\)个士兵时，能够得到的最大战斗力是多少。同时我们记\(sum[i]\)表示前\(i\)个士兵战斗力之和。那么转移方程就是\(dp[i]=min(dp[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c)\)。如果\(k>j\)并且\(k\)比\(j\)更优，那么：

\(dp[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c\leq dp[j]+a*(sum[i]-sum[k])^2+b*(sum[i]-sum[k])+c\)

整理之后得出：

\(\frac{f[k]-f[j]+a*(sum[k]-sum[j])^2-b*(sum[k]-sum[j])}{2*a*(sum[k]-sum[j])}\leq sum[i]\)

然后就是套用斜率优化进DP了

AC代码

/**************************************************************    Problem: 1911    User: czl2333    Language: C++    Result: Accepted    Time:1220 ms    Memory:48180 kb****************************************************************/ #include 
    
     using namespace std;typedef long long ll;bool Finish_read;template
     
      inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}template
      
       inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}template
       
        inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}template
        
         inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}/*================Header Template==============*/#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);const int maxn=2e6+500;int n;int a,b,c;int x[maxn];int l,r;int que[maxn];ll f[maxn],sum[maxn];/*==================Define Area================*/ll Sqr(ll x) {    return x*x;} double Cal(int x,int y) {    return (double)(f[y]-f[x]+a*(Sqr(sum[y])-Sqr(sum[x]))-b*(sum[y]-sum[x]))/(double)(2*a*(sum[y]-sum[x]));} int main() {    read(n);    read(a);read(b);read(c);    for(int i=1;i<=n;i++) {        read(x[i]);    }    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+x[i];    for(int i=1;i<=n;i++) {        while(l
         
          
           Cal(que[r],i)) r--; que[++r]=i; } printf("%lld\n",f[n]); return 0;}