关于单调队列优化和斜率优化动态规划的典型例题及其解法的总结

青丘杨哲 · 2019-04-02 21:05:42 · 个人记录

关于单调队列优化和斜率优化动态规划的典型例题及其解法的总结

在将来的普及组中，将会出现越来越多的需要切实优化复杂度的动态规划题型。从当前的情况来看，单调队列优化和斜率优化是两类编码较简单、难度较小、解法较相近、思路较清晰可见的优化，在普及组中考查的几率最大。因此本篇博文专门整理这两种优化的一些例题和解法。

一、单调队列优化

1.1 概述

单调队列通常可以将朴素算法的时间复杂度降下一个维度，从而避免超时的风险。我们可以利用方程的决策单调性，用单调队列维护队首的最值。倘若发现一个决策i在另一个决策j之前且决策i还不优于决策j，则可以将决策i弹出；反之，如果决策i在决策j之后且决策i优于决策j，则我们可以坚定地将i加入队列。需要注意的是，我们必须要保证整个队列的长度不超过题目所规定的范围。

单调队列优化动态规划的典型例题很多，例如：

· P2216 [HAOI2007]理想的正方形

· P2219 [HAOI2007]修筑绿化带

· P2564 [SCOI2009]生日礼物

1.2.1 例题分析

本题是NOIP2017普及组的压轴题，可见其还是具有一定难度的。但是我们还是能够轻松地推出朴素的转移方程：

令dp[i]表示跳了前i个格子且现在停留在第i个格子时所能获得的最大分数，则：

用单调队列优化，我们发现j随着i单调递增，因此我们只要在dis[i]-dis[j]的值在机器人弹跳的范围内时，让决策j进队即可。

为了使编程简单，我们可以把用于DP的单调队列和用于确定候选集合的单调队列用STL的deque代替，将两个队列的操作合并即可。

因此，我们可以二分g的值，并用上述动态规划的过程去判断g是否符合要求，最终我们就可以得到符合要求的最小的g。此外还有一些细节需要注意，例如中间答案可能超出int的范围、如何判断无法成功等。

1.2.2 参考程序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=500005;
const LL INF=1e18;
int N,d,l,r,mid,dis[MAXN],scr[MAXN];
LL sum,k,dp[MAXN];
bool check(int g){
    for (int i=1;i<=N;i++) dp[i]=-INF;
    deque<int> q;
    int h=0,l=max(d-g,1),r=d+g;
    dp[0]=0;
    for (int i=1;i<=N;i++){
        dp[i]=-INF;
        while (dis[h]+l<=dis[i]){
            while (!q.empty()&&dp[q.back()]<=dp[h]) q.pop_back();
            q.push_back(h++);
        }
        while (!q.empty()&&dis[q.front()]+r<dis[i]) q.pop_front();
        if (!q.empty()&&dis[q.front()]+l<=dis[i]) dp[i]=dp[q.front()]+scr[i];
        if (dp[i]>=k) return true;
    }
    return false;
}
int main(){
    scanf("%d%d%lld",&N,&d,&k);
    for (int i=1;i<=N;i++)
        scanf("%d%d",&dis[i],&scr[i]),sum+=max(0,scr[i]);
    if (sum<k){
        printf("-1");
        return 0;
    }
    r=dis[N];
    while (l<r){
        mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d",l); 
    return 0;
}

二、斜率优化

2.1 概述

有时我们会得出一个二维的转移方程，这个转移方程明显需要复杂度优化，但同时存在i和j的下标项，这时我们就无法使用单调队列优化的。我们需要引进一种新的优化，即斜率优化。

我们可以把方程中所有的项化开，然后依据两个转移中的决策构建不等式，将相同的项消去，再把不等式两边分别整理成只和决策或只和阶段有关的形式，最后除以类似于前缀和的两项，即可进行斜率优化。至于具体的整理过程，我们会在例题的分析过程中呈现。

一旦掌握了斜率优化的基本套路，那么在一道斜率优化题的朴素方程水落石出后，我们就可以轻松地按照这个套路进行不等式化简和编程了。因此，斜率优化并不是那么难。

斜率优化的典型例题也有相当的数量，例如：

· P2120 [ZJOI2007]仓库建设

· P2900 [USACOMar,2008]土地征用

· P3195 [HNOI2008]玩具装箱

· P3628 [APIO2010]特别行动队

· P4072 [SDOI2016]征途

· P4360 [CEOI2004]锯木厂选址

2.2 典型例题

2.2.1 P3195 [HNOI2008]玩具装箱

2.2.1.1 例题分析

本题是一道较为典型的斜率优化题。

令dp[i]表示前i个玩具的答案，sum[i]表示\sum_{j=1}^{i}C[j]，则我们易得DP方程：

其中1≤j≤i-1。

下面开始斜率优化的分析过程：

由于原式中含有多项式的平方项，我们令x[i]=sum[i]+i，y[i]=sum[i]+i+L+1，则原方程化为：

考虑两个决策j，k且满足0≤k<j<i，且决策j优于决策k，则：

因为y[i]递增，所以y[j]-y[k]>0，因此

令p[i]=y[i]，q[i]=dp[i]+y[i]^2，则上式化为

设slope(i,j)表示过点(p[j],q[j])和(p[k],q[k])的斜率，则slope(i,j)>2·x[i]时j一定不比k更优。因此我们只要保证slope(q[h],q[h+1])>2·x[i]即可转移。大功告成。

2.2.1.2 参考程序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=50005;
const int INF=0x7f7f7f;
int N,L,h,t,c[MAXN],q[MAXN];
LL M,s[MAXN],dp[MAXN];
double slope(int i,int j){
    return (dp[j]-dp[i]+(s[j]+M)*(s[j]+M)-(s[i]+M)*(s[i]+M))/(2.0*(s[j]-s[i]));
}
int main(){
    scanf("%d%d",&N,&L),M=L+1,h=t=1;
    for (int i=1;i<=N;i++) scanf("%d",&c[i]);
    for (int i=1;i<=N;i++) s[i]=s[i-1]+c[i];
    for (int i=1;i<=N;i++) s[i]+=i;
    for (int i=1,j;i<=N;i++){
        while (h<t&&slope(q[h],q[h+1])<=s[i]) h++;
        j=q[h],dp[i]=dp[j]+(s[i]-s[j]-M)*(s[i]-s[j]-M);
        while (h<t&&slope(q[t],i)<slope(q[t-1],q[t])) t--;
        q[++t]=i;
    }
    printf("%lld",dp[N]);
    return 0;
}

2.2.2 P2120 [ZJOI2007]仓库建设

2.2.2.1 例题分析

在本题的分析过程中，一些基础的步骤将被省略。

令sum[i]表示x[i]·p[i]的前缀和，sp[i]表示p[i]的前缀和，易得DP方程为：

假设k<j且决策j优于k，则

如此我们即可进行斜率优化。

2.2.2.2 参考程序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1000005;
int N,X[MAXN],P[MAXN],C[MAXN],q[MAXN],h,t;
LL s[MAXN],sp[MAXN],dp[MAXN];
inline double slope(int i,int j){
    return (double)(dp[i]-dp[j]+s[i]-s[j])/(double)(sp[i]-sp[j]);
}
int main(){
    scanf("%d",&N),h=t=1;
    for (int i=1;i<=N;i++){
        scanf("%d%d%d",&X[i],&P[i],&C[i]);
        s[i]=s[i-1]+(LL)X[i]*P[i],sp[i]=sp[i-1]+P[i];
    }
    for (int i=1,j;i<=N;i++){
        while (h<t&&slope(q[h+1],q[h])<X[i]) h++;
        j=q[h],dp[i]=dp[j]+X[i]*(sp[i]-sp[j])-(s[i]-s[j])+C[i];
        while (h<t&&slope(q[t],i)<slope(q[t],q[t-1])) t--;
        q[++t]=i;
    }
    printf("%lld",dp[N]);
    return 0;
}

三、总结

3.1 两种优化的异同

单调队列优化的基本框架为：

while (h<t&&决策单调性) h++;
状态转移；
while (h<t&&决策单调性) t--;
新的决策进队;

而斜率优化的基本框架为：

inline double slope(int i,int j){
    return 推导得到的式子;
}
int main(){
    for (int i=1;i<=N;i++){
        while (h<t&&slope(q[h],q[h+1])<推得式子) h++;
        状态转移；
        while (h<t&&slope(q[t],i)<slope(q[t-1],q[t])) t--;
        新决策进队;
    }

最终斜率优化的实现还是依赖于单调队列，但是单调队列优化的是同一个维度的（都是i或j），而斜率优化则是优化两个维度。

3.2 结语