单调队列优化&斜率优化DP

· · 算法·理论

单调队列优化

单调队列，顾名思义是值随着下标而单调递增/减的序列，是斜率优化、单调决策性优化的基础

显然可以用它来优化的DP具有以下性质：

单调队列中存储的是决策点，就是那些可以向 i 转移的 j，其中每次的队首都是直接转移的

我们使用数组来模拟队列，保存队首为 hd 队尾为 ed，DP时遍历 i=1 ~ n，大致步骤为：

  1. 将队首不符合要求的元素删掉（hd++）
  2. 根据队首的值进行DP转移
  3. 将队尾不如 i 优的决策删掉（tl--）
  4. 存入新决策 i（q_{++tl}=i）

下面用例题来详细说明一下

例1：P3594

题面

长度不超过 d 的区间，可以理解为直接选择长度为 d 的区间修改为 0，因为这样肯定更优

由于这个题问的是区间长度，所以不妨定下区间右端点 r（2 ~ n），找最远的左端点 l

设 f_i 为前 i 个数的最长区间，s_i 是前缀和数组

朴素DP是遍历 1 ~ r-1，找到最小的 l 满足 s_r-s_{l-1}-(s_x-s_{x-d+1}) \le p，其中 x 是在区间 [l,r] 之间的一个元素

显然，想让 l 最小，s_x-s_{x-d+1} 必然最大，所以我们使用单调队列维护这个 x

首先考虑队首，一般情况下队首删除的是 “不符合规定的”，所以如果 q_{hd} 到左端点 l 的距离不足 d，则说明 q_{hd}-d+1<l，此时就可以删掉了，因为删除的区间不在 [l,r] 内

然后考虑队尾，一般队尾删掉的是 “不如当前决策优的”，明确 i>q_{tl}，那么此时如果 s_i-s_{i-d}>s_{q_{tl}}-s_{q_{tl}-d}，则表示决策 i 优于决策 q_{tl}，所以它就可以删除了

最后考虑 l 的更新，如果区间 [l,r] 减去 d 个数仍大于 p，则需要缩小区间 l++，因为队首 hd 的大小随 l 而改变，所以采用嵌套while循环，外层改变 l，内层更新 hd

答案就是对于每个 i 取 max(r-l+1)

Code: 
#include <bits/stdc++.h>
using namespace std;
long long a[2000005],s[2000005],q[2000005];
int main()
{
    long long n,m,d;
    scanf("%lld%lld%lld",&n,&m,&d);
    for(long long i = 1;i <= n;i++)
    {
        scanf("%lld",&a[i]);
        s[i] = s[i - 1] + a[i];
    }
    long long hd = 1,tl = 1,l = 1,maxa = d;
    for(long long i = 1;i <= n;i++)
    {
        long long r = i;
        while(hd <= tl && s[i] - s[i - d] > s[q[tl]] - s[q[tl] - d])
        {
            tl--;
        }
        q[++tl] = i;
        while(hd <= tl && s[i] - s[l - 1] - (s[q[hd]] - s[q[hd] - d]) > m)
        {
            l++;
            while(hd <= tl && q[hd] - l + 1 < d)
            {
                hd++;
            }
        }
        maxa = max(maxa,r - l + 1);
    }
    printf("%lld",maxa);
    return 0;
}

例2：P4954

题面

显然塔越细越高，所以每一层的宽度要小

如果我们从塔底开始堆，那么每一层都有一个宽度上限，这代表可能堆不完，所以从塔顶开始堆，这样只会有下限，一定可以堆完，每包干草的宽度采取倒序输入

设 s_i 为前缀和，f_i 为前 i 包干草能摞的最高高度，由于需要统计上一层的宽度，所以不妨再设一个数组 g_i 表示当前 f_i 对应的这一层的宽度

转移条件为：s_i-s_j \le g_j -> f_i=f_j+1

移项：s_j+g_j \ge s_i，显然要让 s_j+g_j 最小，那么用单调队列维护这个值

对于队首，找到所有决策点中离 i 最近的那个，也就是找满足 s_i-s_{q_{hd}} \ge g_{q_{hd}} 最大的 hd，但是由于不满足这个条件才会跳出while循环，所以最终决策点实际是 q_{hd-1}

转移的时候从 q_{hd-1} 转移，g_i 就是第 q_{hd-1} 到第 i 层干草的宽度和，f_i=f_{q_{hd-1}}+1

对于队尾，在 i>q_{tl} 的前提下，如果 s_i+g_i < s_{q_{tl}}+g_{q_{tl}}，则可以删掉了，因为决策 i 的宽度更小，比 q_{tl} 优

Code: 
#include <bits/stdc++.h>
using namespace std;
long long a[100005],s[100005],q[100005],f[100005],g[100005];
int main()
{
    long long n;
    scanf("%lld",&n);
    for(long long i = n;i >= 1;i--)
    {
        scanf("%lld",&a[i]);
    }
    for(int i = 1;i <= n;i++)
    {
        s[i] = s[i - 1] + a[i];
    }
    long long hd = 1,tl = 1;
    for(long long i = 1;i <= n;i++)
    {
        while(hd <= tl && s[i] - s[q[hd]] >= g[q[hd]])
        {
            hd++;
        }
        g[i] = s[i] - s[q[hd - 1]];
        f[i] = f[q[hd - 1]] + 1;
        while(hd <= tl && s[i] + g[i] < s[q[tl]] + g[q[tl]])
        {
            tl--;
        }
        q[++tl] = i;
    }
    printf("%lld",f[n]);
    return 0;
}

斜率优化

斜率：假设直线 l 经过点 (x_1,y_1) 和 (x_2,y_2)，则它的斜率 k=\frac{y_1-y_2}{x_1-x_2}

斜率优化就是利用斜率的单调性来优化DP，有点抽象，通过例题理解

例题：P3195

题面

（一）代数法理解

设 s 数组为前缀和，f_i 表示前 i 件玩具的最小费用，朴素DP式子：f_i=min(f_j+(s_i-s_j-1-L)^2)

为了方便表述，我们把 L+1，去掉 min，并拆开式子把同类型的放在一起，变为：f_i=(s_i^2-2s_iL)+(f_j+(s_j+L)^2)-2s_is_j

设有 x<y 且决策 y 优于 x，把它们代入上式，得到：(f_y+(s_y+L)^2)-2s_is_y \le (f_x+(s_x+L)^2)-2s_is_x

此时我们把含有 i 的项和其他的分离 （根参分离），移项等后变为：2s_i \ge \frac{(f_y+(s_y+L)^2)-(f_x+(s_x+L)^2)}{s_y-s_x}（尽量将式子模式化，保证分子分母都是 y-x 的形式）

为了形成斜率的格式，我们令 g(i)=f_i+(s_i+L)^2,h(i)=s_i，则式子又变成： 2s_i \ge \frac{g(y)-g(x)}{h(y)-h(x)}，即关于点 x 和点 y 的斜率式，这里设 kk_i=2s_i

然后，把所有的点放到二维平面上，它们的下凸包就是所有可能的决策，原因可以通过三个点分类讨论来推广，这里不再赘述（注意并非所有的都是下凸包，上式要求点 x 和点 y 的斜率 \le kk_i 才是，如果变成 \ge，就是上凸包了）

我们要对一个问题进行优化，要关注两件事：正确性和单调性，对于斜率优化，正确性显然，而单调性我们看下凸包：

橙色线的斜率逆时针单调递减，灰蓝色的点不选是因为一定能找到两个湖蓝色的点使之不可能成为最优决策

下面来找最优决策点，这个点要满足与左边的点构成的边的斜率 \le kk_i，与右边的斜率 >kk_i，使用二分找到第一条斜率 >kk_i 的边，其左端点即为最优决策点

（二）几何法理解

原本DP方程：f_i=(s_i^2-2s_iL)+(f_j+(s_j+L)^2)-2s_is_j，把它移项变成 y=kx+b的形式，其中 y 是含 j 的项，kx 为含 i,j 的项，b 为含 i 的项，式子变成：(2s_i)s_j+(f_i-s_i^2+2s_iL)=(f_j+(s_j+L)^2)

我们要使 f_i 最小，就是要让 b 最小，也就是在所有决策点（下凸包） 中找到一点，使一条斜率固定的直线经过改点时，截距最小

显然上图中，红色点的截距最小，那么它就是最优决策点

（三）代码实现

使用单调队列维护下凸包点集，大致分为三步：

  1. 择优筛选，找到第一个斜率 > 2s_i 的边，此时 q_{hd} 就是最优决策
  2. 利用 q_{hd} 更新 f_i
  3. 加入决策点 i，随之更新点集，使其满足下凸包性质 （如果点集的倒数第二个点和 i 形成的边可以把队尾删掉，那么就 tl--）

可以这样判断队尾可删：xl(q[tl - 1],i) <= xl(q[tl - 1],q[tl])（xl函数求斜率）

时间复杂度：O(nlogn)

Code: 
#include <bits/stdc++.h>
using namespace std;
long long n,m,s[50005],f[50005],q[50005];
long long X(long long a)
{
    return s[a];
}
long long Y(long long a)
{
    return f[a] + (s[a] + m) * (s[a] + m);
}
long long xl(long long a,long long b)
{
    return (Y(b) - Y(a)) / (X(b) - X(a));
}
int main()
{
    scanf("%lld%lld",&n,&m);
    m++;
    for(long long i = 1;i <= n;i++)
    {
        long long a;
        scanf("%lld",&a);
        s[i] = s[i - 1] + a + 1;
    }
    long long hd = 1,tl = 1;
    for(long long i = 1;i <= n;i++)
    {
        while(hd <= tl - 1 && xl(q[hd],q[hd + 1]) <= 2 * s[i])
        {
            hd++;
        }
        f[i] = f[q[hd]] + (s[i] - s[q[hd]] - m) * (s[i] - s[q[hd]] - m);
        while(hd <= tl - 1 && xl(q[tl - 1],i) <= xl(q[tl - 1],q[tl]))
        {
            tl--;
        }
        q[++tl] = i;
    }
    printf("%lld",f[n]);
    return 0;
}

注意：因为至少两个点才能组成一条线，所以while循环条件为 hd \le tl-1，否则会出现 \frac{y}{0} 的尴尬情况（别问我怎么知道的喵

其实还可以按照决策单调性再优化，不过还没遇到这样的题，遇到了回来补

（四）一些注意点

  1. 写出朴素DP方程后，应该先推式子，看能否出现 \frac{Y(i)-Y(j)}{X(i)-X(j)} 的形式
  2. 根据最后推出的斜率方程，不定斜率是 \ge kk_i 还是 \le kk_i，来确定决策是在上凸包还是下凸包；还可以根据DP方程求 max/min 知道维护上凸还是下凸（此处“/”两边分别对应）
  3. 如果发现 X(i)=X(j) 的非严格单调情况，则求斜率的时候就不能直接除，应改成return Y(j) >= Y(i) ? inf : -inf
  4. 有时队列初始需要加入一个初值，一般是 f_0

（五）单调性

如P3195，它的 X(i)=s_i 单增，所以满足单调性可以优化

如果 x(i) 没有单调性，那么无法使用单调队列优化，所以采取分治/平衡树（不会哈）

如果 kk_i 没有单调性，此时仍可以用单调队列维护，但是不知道在哪里能取得最优决策点，所以只能保留整个凸包，不能删除队首、队尾，需要二分

均不单调时用平衡树维护前驱后继，查询 kk_i 即可（也不会捏）

附：来自神犇的警句

从哪里转移，主要是看dp方程如何设的，而非是一定的，只是是一般在 q_{left} 的位置