单调队列优化DP

0.前言

本文章例题出自于蓝书，优化方案来自许多博客（但我忘了呜呜呜）

1.单调队列概念与怎么优化

单调队列，我们先来看他是用来干什么的。

单调队列主要用于维护两端指针单调不减的区间最值。 ——oiwiki

对于一般的特殊DP方程，我们可以进行优化。

他优化的是下面的一类DP方程，其中：

$$\text{得到的方程：} f[i]=\min\limits_{L(i)\le j \le R(i)}{(f[j]+a[i]+b[j])}$$

$$\text{因为i是外层循环定值，变形为：} f[i]=\min\limits_{L(i)\le j \le R(i)}(f[j]+b[j])+a[i]$$

其中min可以替换为max

设$ds[j]=f[j]+b[j]$，因为$ds[j]$与$i$ 完全无关，所以有下式：

$$f[i]=\min\limits_{L(i)\le j \le R(i)}(ds[j])+a[i]$$

由于$ds[j]$仅与$j$有关，与$i$无关，那么我们只需要算一遍$ds[j]$就可以用于全部的$f[i]$计算，不用一个一个去枚举。

朴素的想法是每一次遍历$i$的时候取计算$\min\limits_{L(i)\le j \le R(i)}(ds[j])$，但是这里有大量的重复计算，我们可以用单调队列优化这个计算，可以观察到$j\in [L(i),R(i)]$是一个滑动窗口，我们可以维护滑动窗口上的最值。

• 如果是求最小，我们应维护的是$ds[j]$单调上升的单调队列
• 如果是求最大，我们应维护的是$ds[j]$单调下降的单调队列

如何维护？我们把计算出来的值一个一个压进单调队列，

• 如果是当前的最值，前面计算和不在范围的我们要全部弹走。
• 若要最值，队首就是最值。
• 加入新决策时，先检查加入后是否满足单调性，处理完后那我们放进队尾

这样，队首即为我们想要的$ds[j]$。让后就可以更新$f[i]$，这样，我们从朴素的$O(n^2)$变为了$O(n)$。

$ds[j]$的值计算必须与$i$完全无关！

第二个就是方程中某些具有单调性，可以根据性质发掘出来。

我们来看例题

1.例题引入

P10978

有一段长度为$n$ 的序列和$m$ 个人，每个位置只能染色一次，每个人都有一个位置。这些人可以选择一段长度不超过$L_i$ 并且包括自己位置$S_i$的一段区间进行染色。每个人对一个位置的贡献是$P_i$ 。求最大贡献。
数据范围：$1\le n\le 100,1\le m\le 16000$

我们先根据$S_i$进行排序，这样的话每个人染色的区间一定在上一个工匠粉刷的区间之后，这样就可以线性DP了！

不难有状态$f(i,j)$表示前$i$个人染色$[1,j]$（可以有空着不刷，没说必须刷完）能获得的最大报酬。

不难有转移方程：

1. 不染色罚坐，有$f(i,j)=f(i-1,j)$
2. 第$j$个点可以不刷，有$f(i,j)=f(i,j-1)$
3. 第$i$个人刷$[k+1,j]$，根据题目条件有区间长度$len\le L_i$且$S_{i }\in[k+1,j]$。也就是说$k+1\le S_{i}\le j \text{并且} j-k\le L_i$ ，我们变变形，就有如下转移方程：

$$f(i,j)=\max\limits_{j-L_{i} \le k \le S_i-1}{f(i-1,k)+P_{i}\times (j-k)},\text{其中}j\ge S_i$$

我们观察第三个式子，我们和上面的式子来做个比较：

$$f[i]=\min\limits_{L(i)\le j \le R(i)}{(f[j]+a[i]+b[j])}$$

我们发现这个式子十分甚至九分的详细，我们可以仿照上面把$P_{i} \times j$提出来，因为在这里我们朴素用3层循环，在循环$k$的时候$j$是不变的，故可以提出来。

$$\text{变形后：}f(i,j)=P_{i} \times j + \max\limits_{j-L_{i} \le k \le S_i-1}{(f(i-1,k)-P_{i}\times k}),\text{其中}j\ge S_i$$

当$j$增大时，$k$的上界$S_i-1$不变，下界$j-L_i$变大。那么这个就很像一个滑动窗口，特殊点就在于是一个左端点不断减小，右端点不变的滑动窗口。我们可以维护一个$k$单调递增，$f(i-1,k)-P_{i}\times k$单调递减的一个

如何维护？

1. 当$j$变大，检查队头，把之前计算过的小于$j-L_i$的决策出队。
2. 查询最优的$f(i-1,k)-P_{i}\times k$，我们只需要查队头就行，因为维护的是单调递减的滑动窗口。
3. 当要添加新决策，在队尾先检查$f(i-1,k)-P_{i}\times k$单调性让后在加入

很开头我们提出的维护单调队列的方法十分的相似。

对于本题来说，当开始循环$j$的时候，建立一个空单调队列，先把$[max(S_i-L_i)，S_i-1]$的决策依次加入候选集合，让后检查决策合法性，取队头转移，每个决策至多进入弹出1次，故时间复杂度均摊$O(1)$，故时间复杂度$O(nm)$。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MN=16005;
struct node{
    int l,p,s;
}a[MN];
int n,m;
int f[MN][MN],q[MN];
bool cmp(node x,node y){
    return x.s<y.s;
}

int calc(int i,int k){
    return f[i-1][k]-a[i].p*k;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i].l>>a[i].p>>a[i].s;
    }
    sort(a+1,a+1+m,cmp);//先排序
    for(int i=1;i<=m;i++){
        int l=1,r=0;
        for(int k=max(0,a[i].s-a[i].l);k<=a[i].s-1;k++){
            // 加决策并维护里面的单点递减
            while(l<=r&&calc(i,q[r])<=calc(i,k)) r--;
            q[++r]=k;
        }
        for(int j=1;j<=n;j++){
            f[i][j]=max(f[i-1][j],f[i][j-1]);//罚坐与不涂
            if(j>=a[i].s){//如果当前j可以进行第三个转移方程
                while(l<=r&&q[l]<j-a[i].l){//排除过时决策
                    l++;
                }
                if(l<=r){//如果队不为空，转移
                    f[i][j]=max(f[i][j],calc(i,q[l])+a[i].p*j);
                }
            }
        }
    }
    cout<<f[m][n];
    return 0;
}

请读者阅读完本题题解后和最开始我们提出的优化方法进行比较，观察其思想是如何体现的。

2.单调队列优化多重背包

是是是我知道你会二进制优化，但是我要是限制复杂度$O(nm)$你又不会了。
这一部分教学借鉴了知乎宫水三叶的讲解

给定$n$种物品，第$i$种物品的体积为$V_i$，价值为$W_i$，并且有$C_i$个，背包容积$M$，要求选若干个物品进背包，确保背包不会炸掉的情况下价值总和最大。

首先还是用类似于01背包单维空间的定义：$f[i]$代表容量不超过$i$的最大价值

目标：$f[m]$

朴素的转移想法，我们遍历当前容量能够装多少件该物品，让后从所有情况中取最优。

但事实上，转移只会发生在「对当前物品体积取余相同」的状态之间。——宫水三叶

例如我们遍历$1\rightarrow 10$，物品价值和体积均为2，数量为3，发现有如下规律：

• $f[10]$由$f[8],f[6],f[4]$转移过来
• $f[9]$由$f[7],f[5],f[3]$转移过来
• $\dots$
• $f[5]$由$f[3],f[1]$转移过来
• $f[3]$由$f[1]$转移过来
• $f[2]$由$f[0]$转移过来

即某个状态$f[x]$由$V_{i}\mod x$转移过来（$V_i$为体积，$x$即背包容量），并且比$i$小，数量不超过物品个数的状态值所更新。

那么，我们可以把倒序循环$j$改为对每个余数$u\in[0,V_i-1]$，倒序循环$p=⌊(M-u)/V_i​⌋\rightarrow 0$，对应的状态就是$j=u+p\times V_i$，不难有状态转移方程

$$f[j]=\max\limits_{p-C_{i} \le k \le p-1}(f[u+k\times V_i]+(p-k)\times W_i)$$

不难发现这个转移方程和上一题几乎一模一样，处理方法也是同理的，那么细节就不说了，代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MN=150,MM=1e5+15;
int n,m;
int v[MN],w[MN],c[MN];
int q[MM],f[MM];
int clac(int i,int u,int k){
    return f[u+k*v[i]]-k*w[i];
}
int main(){
    memset(f,128,sizeof(f));
    f[0]=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i]>>c[i];
        for(int u=0;u<v[i];u++){
            int l=1,r=0;
            int maxp=(m-u)/v[i];
            for(int k=maxp-1;k>=max(maxp-c[i],0);k--){
                while(l<=r&&clac(i,u,q[r])<=clac(i,u,k)) r--;
                q[++r]=k;
            }
            for(int k=maxp;k>=0;k--){
                while(l<=r&&q[l]>k-1)l++;
                if(l<=r) f[u+k*v[i]]=max(f[u+k*v[i]],clac(i,u,q[l])+k*w[i]);
                if(k-c[i]-1>=0){
                    while(l<=r&&clac(i,u,q[r])<=clac(i,u,k-c[i]-1))r--;
                    q[++r]=k-c[i]-1;
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++){
        ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;
}

3.另一道例题洛谷P2569

通过一段时间的观察，$\text{lxhgww}$ 预测到了未来$T$ 天内某只股票的走势，第$i$ 天的股票买入价为每股$AP_i$，第$i$ 天的股票卖出价为每股$BP_i$（数据保证对于每个$i$，都有$AP_i \geq BP_i$），但是每天不能无限制地交易，于是股票交易所规定第$i$ 天的一次买入至多只能购买$AS_i$ 股，一次卖出至多只能卖出$BS_i$ 股。
另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔$W$ 天，也就是说如果在第$i$ 天发生了交易，那么从第$i+1$ 天到第$i+W$ 天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过$\text{MaxP}$。
在第$1$ 天之前，$\text{lxhgww}$ 手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，$T$ 天以后，$\text{lxhgww}$ 想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？

不难有状态$f(i,j)$表示到了第$i$天，手上持有第$j$份股票赚到最多的钱数。

目标：$\max\limits_{j=1}^{maxp}f[n][j]$

考虑1天共有4个决策，分别是凭空买（之前没买过股票），今天不交易，凭之前的基础买入和卖出。
那么状态转移方程也就如下：

1. 凭空买：$f(i,j)=\,-AP_{i}\times j \quad \text{其中}j\le AS_i$
2. 不交易：$f(i,j)=max(f(i-1,j))\quad \text{其中}j\le maxp$
3. 买入：$f(i,j)=\max\limits_{j-AS_{i}\le k \le j}f(i-w-1,k)-AP_{i}\times (j-k) \quad \text{其中}j\le maxp$
4. 卖出：$f(i,j)=\max\limits_{j \le k \le j+BS_{i}}f(i-w-1,k)+BP_{i}\times (j-k) \quad \text{其中}j\le maxp$

初始化全部为负无穷。

我们观察方程式，不难发现和之前还是一样的处理逻辑，把$j$提出来，里面的式子就变为了只和$k$有关的量，用单调队列优化即可。

故代码如下，想必你一定借助上面的代码能看懂，这里将不用提供注释了。

#include<bits/stdc++.h>
using namespace std;
const int MN=2015;
struct youaremyidolQUEUE{
    int ap,bp,as,bs;
}d[MN];
int f[MN][MN],n,m,w,q[MN],ql,qr;

bool isnotokap(int i,int j,int k){
    return f[i-w-1][k]+d[i].ap*k<=f[i-w-1][j]+d[i].ap*j;
}

bool isnotokbp(int i,int j,int k){
    return f[i-w-1][k]+d[i].bp*k<=f[i-w-1][j]+d[i].bp*j;
}

int main(){
    memset(f,128,sizeof(f));
    cin>>n>>m>>w;//m为maxp
    for(int i=1;i<=n;i++){
        cin>>d[i].ap>>d[i].bp>>d[i].as>>d[i].bs;
    }
    for(int i=1;i<=n;i++){
        
        for(int j=0;j<=d[i].as;j++){
            f[i][j]= -1*d[i].ap*j;
            
        }
        for(int j=0;j<=m;j++){
            f[i][j]=max(f[i][j],f[i-1][j]);
        }
        if(i<=w) continue;
        ql=1,qr=0;
        for(int j=0;j<=m;j++){
            while(ql<=qr&&q[ql]<j-d[i].as) ql++;
            while(ql<=qr&&isnotokap(i,j,q[qr])){
                qr--;
            }
            q[++qr]=j;
            if(ql<=qr){
                f[i][j]=max(f[i-w-1][q[ql]]+q[ql]*d[i].ap-d[i].ap*j,f[i][j]);
            }
        }
        ql=1,qr=0;
        for(int j=m;j>=0;j--){
            while(ql<=qr&&q[ql]>j+d[i].bs) ql++;
            while(ql<=qr&&isnotokbp(i,j,q[qr])){
                qr--;
            }
            q[++qr]=j;
            if(ql<=qr){
                f[i][j]=max(f[i-w-1][q[ql]]+q[ql]*d[i].bp-d[i].bp*j,f[i][j]);
            }
        }
    }
    int ans=-2e9;
    for(int i=0;i<=m;i++){
        ans=max(ans,f[n][i]);
    }
    cout<<ans;
    return 0;
}

4.总结

在第一部分中我们提到的模型，实际上就是1D1D动态规划模型，就是类似于如下：

$$f(i)=min/max(g(j)+w(i,j))\quad 1\le j < i$$

如果$w(i,j)$为一次函数，那么我们可以用单调队列进行优化。或者不是多项式但有单调性，我们也可以进行优化。

回忆LIS，我们发现他们有着类似的结构，但是为什么LIS不能用单调队列进行求解呢？这是因为其中有一个关系在$a[j]<a[i]$，这个关系在成立的时候$w=1$否则$w=0$，不难看出违反了上面的最重要的一条，$w$必须与$i$无关。

那么这个题怎么解呢，我们可以使用DP+二分的方法进行求解，这样的时间复杂度就是$O(nlogn)$，感兴趣可以回看NOIP1999导弹拦截这道题，观察第一问的转移方程，思考为什么不能用单调队列求解，为什么使用二分，会有新收获。

在某些题中，1D/1D模型不在适用，就要自行取挖掘性质进行优化，例如P10977，就要发掘性质用堆（或multiset）和单调队列优化，可以看zhouruoheng的题解来理解发掘单调性的奥妙。

完结撒AC！