1. IT分享知识网首页

单调队列

老牧童 • • 未分类 • 阅读 161

单调队列单调队列队列中的元素其对应在原来的列表中的顺序必须是单调递增的队列中元素的大小必须是单调递（增、减、甚至是自定义也可以）（一）单调队列基础Example1:滑动窗口LuoguP1886有一个长为$n$的序列$a$，以及一个大小为$k$的窗口。现在这个从左边开始向右滑动，每

大家好，欢迎来到IT知识分享网。

单调队列

  1. 队列中的元素其对应在原来的列表中的顺序必须是单调递增的
  2. 队列中元素的大小必须是单调递（增、减、甚至是自定义也可以）

（一）单调队列基础

Example1: 滑动窗口 Luogu P1886

有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。

现在这个从左边开始向右滑动，每次滑动一个单位。

求出每次滑动后窗口中的最大值和最小值。

以求最小值为例：

如果队尾的数字要大于要进队列的数字，那么队尾的数字肯定不会成为后面窗口中的最小值了，所以直接出队列。

那么显然我们要维护一个单调不降的队列。

当队首的数字与当前数字的下标距离大于 \(k-1\) 时，队首数字就必须出队列。

当前数字进入队列后，以当前数字为窗口尾巴的序列的最小值就是队首的数字。

由上述过程可得：

单调队列与普通队列不一样的地方就在于单调队列既可以从队首出队，也可以从队尾出队。

所以我们STL中的双端队列deque派上用场了！

deque<int> q;
int n,k,a[1000010];

void getmin()
{
    for(int i=1;i<=k;i++)
    {
        while(!q.empty()&&a[i]<a[q.back()])
            q.pop_back();
        q.push_back(i);
    }
    printf("%d",a[q.front()]);
    
    for(int i=k+1;i<=n;i++)
    {
        if(q.front()+k<=i) q.pop_front();
        while(!q.empty()&&a[i]<a[q.back()])
            q.pop_back();
        q.push_back(i);
        printf(" %d",a[q.front()]);
    }
}

void getmax()
{
    for(int i=1;i<=k;i++)
    {
        while(!q.empty()&&a[i]>a[q.back()])
            q.pop_back();
        q.push_back(i);
    }
    printf("%d",a[q.front()]);
    
    for(int i=k+1;i<=n;i++)
    {
        if(q.front()+k<=i) q.pop_front();
        while(!q.empty()&&a[i]>a[q.back()])
            q.pop_back();
        q.push_back(i);
        printf(" %d",a[q.front()]);
    }
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    
    getmin();
    while(!q.empty()) q.pop_front();
    printf("\n");
    
    getmax();
    printf("\n");
    
    return 0;
}

Example2: 最大子序和 AcWing135

输入一个长度为 \(n\) 的整数序列，

从中找出一段不超过 \(m\) 的连续子序列，

使得整个序列的和最大。

根据例题的解法，我们可以轻易想到这道题应该用单调队列来做。

同样地，我们先枚举右端点 \(i\)，那么此时问题就转化为了：

找到一个左端点 \(j\)，其中 \(j \in [i-m,i-1]\)，并且 \(sum[j]\) 最小。

维护一个 单调不降 的队列，记录左端点，对这个队列有以下三种操作：

  1. 判断队列中元素的位置是否与 \(i\) 超出 \(m\) 的范围，若超出则不成立，出队；
  2. 此时队头为 右端点为 \(i\)，左端点为 \(j\) 时 的最优情况，更新 \(ans\)；
  3. 不断删除队尾元素，直至队尾所对应的 \(sum\) 小于 \(s[i]\)，然后将 \(i\) 进队。
// a 即为前缀和数组 sum
int ans=a[1];
for(int i=1;i<=n;i++)
{
    if(!q.empty()&&q.front()+m<i) q.pop_front();
    if(!q.empty()) ans=max(ans,a[i]-a[q.front()]);
    while(!q.empty()&&a[q.back()]>=a[i]) q.pop_back();
    q.push_back(i);
}
printf("%d\n",ans);

Exercise1: 切蛋糕 Luogu P1528

今天是小 Z 的生日，同学们为他带来了一块蛋糕。

这块蛋糕是一个长方体，被用不同色彩分成了 \(n\) 个相同的小块，每小块都有对应的幸运值。

小 Z 作为寿星，自然希望吃到的蛋糕的幸运值总和最大，但小 Z 最多又只能吃 \(m(m\le n)\) 小块的蛋糕。

请你帮他从这 \(n\) 小块中找出 连续 的 \(k(1 \le k\le m)\) 块蛋糕，使得其上的总幸运值最大。

简化题意：在数列 \(\{p_n\}\) 中，找出一个子段 \([l,r](r-l+1\le m)\)，最大化 \(\sum_{i=l}^rp_i\)。

然后就和 例题2 一模一样了。

Exercise2: Flowerpot S Luogu P2698 [USACO12MAR]

给出 \(n\) 滴水的坐标，\(y\) 表示水滴的高度，\(x\) 表示它下落到 x轴 的位置。

每滴水以每秒 \(1\) 个单位长度的速度下落。你需要把花盆放在 \(x\) 轴上的某个位置，

使得从被花盆接着的第 \(1\) 滴水开始，到被花盆接着的最后 \(1\) 滴水结束，之间的时间差至少为 \(d\)。

我们认为，只要水滴落到 x轴 上，与花盆的边沿对齐，就认为被接住。

给出 \(n\) 滴水的坐标和 \(d\) 的大小，请算出最小的花盆的宽度 \(w\)。

单调队列

假设已知 \(w\)，如何求时间差是否 \(\geq d\)？

显然，判断每个长度为 \(w\) 的区间，最早落下的水滴和最晚落下的水滴时间之差是否 \(\geq d\) 即可

那么我们 只需要知道一段区间内的最大值与最小值，也就将题目转化为 例题1 了

将每一滴水滴按照 \(x\) 的大小 升序排列，单调队列维护 \(y\) 值的最大与最小。

bool check(int w)
{
    deque<int> q1,q2; // q1表示最大值，q2表示最小值
    
    for(int i=1;i<=n;i++)
    {
        if(!q1.empty()&&a[q1.front()].x+w<a[i].x) q1.pop_front();
        while(!q1.empty()&&a[q1.back()].y<=a[i].y) q1.pop_back();
        
        if(!q2.empty()&&a[q2.front()].x+w<a[i].x) q2.pop_front();
        while(!q2.empty()&&a[q2.back()].y>=a[i].y) q2.pop_back();
        
        q1.push_back(i); q2.push_back(i);
        if(a[q1.front()].y-a[q2.front()].y>=d) return true;
    }
    return false;
}

题目中求最小的 \(w\)，可以二分 \(w\) 出现的的情况，找到最小值就行了。

这里可以将 \(r\) 的初值定为最大的 \(x+1\)，如果最终 \(r\) 仍为最大的 \(x+1\)，那就说明没有答案，输出 \(-1\)。

int l=1,r=a[n].x+1,ans;
while(l+1<r)
{
    int mid=l+r>>1;
    if(check(mid)) r=mid;
    else l=mid;
}

if(r==a[n].x+1) puts("-1");
else if(check(r)) printf("%d\n",r);
else printf("%d\n",l);

Tips: 每次二分答案判断时，队列记得清空！！！

（二）单调队列优化 DP

一、单调队列优化 线性DP

如果你觉得 线性DP 学得并不够好，可以先来 \(10\) 道 线性DP经典题 练练手~~

回顾一下 单调队列基础 中的 例题2 ，如果用 DP 的状态转移思想来看，可得如下状态转移方程：

\[ans = \max _{1\leq i\leq N} \left\{ sum[i] – \min _{i-m\leq j\leq i-1} \{ sum[j\}\right\} \]

这里就不过多解释了，大家一定可以自行理解的。

其中，我们将 \(i\) 当作 状态，\(j\) 当作 决策，这样就将 单调队列与动态规划联系起来了。

下面，我们来看几道例题：

Example: 围栏 AcWing298

有 \(N\) 块木板从左到右排成一行，有 \(M\) 个工匠对这些木板进行粉刷，每块木板至多被粉刷一次。

第 \(i\) 个木匠要么不粉刷，要么粉刷包含木板 \(S_i\) 的，长度不超过 \(L_i\) 的连续的一段木板，

每粉刷一块可以得到 \(P_i\) 的报酬。不同工匠的 \(S_i\) 不同。

请问如何安排能使工匠们获得的总报酬最多。

先将工匠按照 \(S_i\) 排序，这样每个工匠粉刷的木板就一定在上一个工匠之后了，

于是就可以按照顺序进行 线性DP。

状态：\(f[i][j]\)：前 \(i\) 个工匠粉刷了前 \(j\) 块木板（可以有的不刷），所获得的最大报酬

状态转移：

  1. 第 \(i\) 个工匠什么也不刷：\(f[i][j]=f[i-1][j]\)

  2. 不刷第 \(j\) 块木板：\(f[i][j]=f[i][j-1]\)

  3. 第 \(i\) 个工匠刷了 \([k+1,j]\) 之间的木板：

    \[f[i][j]=\max_{j-L_i\leq k\leq S_i-1}\{ f[i-1][k]+(j-k)\times P_i\}，其中j\leq S_i \]

如果暴力枚举 \(i,j,k\)，时间复杂度为 \(O(mn^2)\)，而\(1\leq n\leq 16000\)，显然超时。

那么我们来考虑如何 优化第三个转移方程：

仿照前面所说，\(i\) 是一个定值，将 \(j\) 当作状态，\(k\) 为决策，于是就可以把 \(\max\) 中的形式变换一下：

\[f[i-1][k]+(j-k)\times P_i = j \times P_i+f[i-1][k]-k\times P_i \]

因此，在枚举 \(k\) 时，\(j \times P_i\) 也成为了定值，状态转移方程就可变为：

\[f[i][j]=j \times P_i + \max_{j-L_i\leq k \leq S_i-1} \{f[i-1][k]-k\times P_i \} \]

经过比较，可以轻易发现，这个方程与前面提到的 例题2 几乎一模一样。

本题增加了一维枚举工匠，对结果没有任何影响，至于 \(P_i\)，是一个已知量，

因此，我们可以考虑像 例题2 一样，用单调队列进行优化。

具体操作几乎没有发生任何变化，如下：

  1. 判断队列中元素的位置是否与 \(j\) 超出 \(L_i\) 的范围，若超出则不成立，出队；
  2. 此时队头为 第 \(i\) 个工匠刷了 \([k+1,j]\) 之间的木板 的最优情况，更新 \(f[i][j]\)；
  3. 不断删除队尾元素，直至队尾所对应的 \(f[i-1][k]+(j-k)\times P_i\) 大于 \(f[i][j]\)，然后将 \(i\) 进队。

具体看代码注释吧：

for(int i=1;i<=m;i++) // 枚举第i名工匠
{
    for(int j=0;j<=n;j++) // 枚举所刷木板的右端点j
    {
        f[i][j]=f[i-1][j]; // 第i名工匠什么也不刷
        if(j) f[i][j]=max(f[i][j],f[i][j-1]); // 不刷第j块木板

        int l=a[i].l,p=a[i].p,s=a[i].s;
        if(!q.empty()&&q.front()+l<j) q.pop_front(); // 左右端点距离超过l，这名工匠不能刷
        if(!q.empty()&&j>=s) // 左端点>s，满足这名工匠必须刷第s块木板的要求，更新f[i][j]
        {
            int k=q.front();
            f[i][j]=max(f[i][j],f[i-1][k]+(j-k)*p);
        }
        if(j<s) // 由j-l<=k<=s-1得，进队的木板都在s左边，因此<s的j才能进队
        {
            while(!q.empty()&&f[i-1][q.back()]+(j-q.back())*p<=f[i-1][j])
                q.pop_back(); // 单调队列板子，不满足单调性的左端点全部出队
            q.push_back(j);
        }
    }
}

最后输出 \(f[m][n]\) 即可。

Exercise1: Tower of Hay G Luogu P4954 [USACO09OPEN]

Exercise2: 股票交易 Luogu P2569 [SCOI2010]

Expand: 裁剪序列 AcWing299

二、单调队列优化 多重背包

如果你不太清楚 背包问题，可以来复习一下 基础动态规划 （万字心血之作）

当然，如果你仅仅 不太清楚多重背包的解法，往下看就好了~

  • 直接拆分法

Example1: 完全多重背包问题I AcWing4

有 \(N\) 种物品和一个容量是 \(M\) 的背包。

第 \(i\) 种物品最多有 \(s_i\) 件，每件体积是 \(v_i\)，价值是 \(w_i\)。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。 \(0<N,V\leq 100\)，\(0<v_i,w_i,s_i\leq 100\)。

将第 \(i\) 种物品看作独立的 \(s_i\) 个物品，转化为 共有 \(\sum_{i=1} ^N s_i\) 个物品的 01背包。

当然这种算法的时间复杂度非常高，达到了 \(O(NM\times \sum_{i=1} ^N S_i)\)。

不过本题数据量非常小，可以过。

for(int i=1;i<=n;i++)
    for(int j=1;j<=s[i];j++)
        for(int k=m;k>=v[i];k--)
            f[k]=max(f[k],f[k-v[i]]+w[i]);

最后输出 \(f\) 数组中的最大值即可。

int ans=0;
for(int i=1;i<=m;i++)
    ans=max(ans,f[i]); 
printf("%d\n",ans);
  • 二进制拆分法

Example2: 完全多重背包问题II AcWing5

有 \(N\) 种物品和一个容量是 \(M\) 的背包。

第 \(i\) 种物品最多有 \(s_i\) 件，每件体积是 \(v_i\)，价值是 \(w_i\)。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。 \(0<N\leq 1000\)，\(0<V\leq 2000\)，\(0<v_i,w_i,s_i\leq 2000\)。

和上道例题相比，数据量扩大了，因此上个方法就不再适用了。

那么该如何做呢？

我们知道，从 \(2^0,2^1,2^2,\cdots,2^{k-1}\) 这 \(k\) 个 \(2\) 的整数次幂中选择若干个相加，

可以表示出 \(0\sim 2^k-1\) 之间的任何整数。

现在，我们求出满足 \(2^0+2^1+\cdots+2^p\leq S_i\) 的最大整数 \(p\)，

设 \(R_i=C_i-2^0-2^1-\cdots-2^p\)，那么：

  1. \(2^0+2^1+\cdots+2^p+2^{p+1}> S_i\)，移项变换就可以得到 \(2^{p+1}>R_i\)。

    因此，从 \(2^0,2^1,\cdots,2^p\) 中选出若干个相加，就可以表示出 \(0\sim R_i\) 中的任何整数。

  2. 根据 1 的结论，如果我们从 \(2^0,2^1,\cdots,2^p\) 以及 \(R_i\) 中选择若干个相加，

    就可以表示出 \(R_i\sim R_i+2^{p+1}-1\) 之间的任何整数。

    根据 \(R_i\) 的定义，\(R_i+2^{p+1}-1=S_i\) （移项和 \(2\) 的从 \(0\) 开始连续整数次幂相加规律，不再证明）

    因此，我们可以表示出 \(R_i\sim S_i\) 之间的任何整数。

综上，我们可以把数量为 \(S_i\) 的第 \(i\) 种物品拆成 \(p+2\) 个物品，它们的体积分别为：

\[2^0\times V_i,2^1\times V_i,\cdots,2^p\times V_i,2^{R_i}\times V_i \]

它们可以凑成 \(0\sim S_i\times V_i\) 之间所有能被 \(V_i\) 整除的数，并且不能凑成大于 \(S_i\times V_i\) 的数。

这就等价于原问题中体积 \(V_i\) 的物品可以使用 \(0\sim S_i\) 次。

由于每一个物品被拆成了 \(\log S_i\) 个，故时间复杂度为 \(O(NM\times\sum _{i=1} ^N \log S_i)\)，本题可过。

for(int i=1;i<=n;i++)
{
    if(s[i]*v[i]>m)
    {
        for(int c=0;c<=m;c++)
            if(c>=v[i]) f[c]=max(f[c],f[c-v[i]]+w[i]);
    }
    else
    {
        int k=1,rest=s[i];
        while(k<=rest)
        {
            for(int c=m;c>=0;c--)
                if(c-k*v[i]>=0) f[c]=max(f[c],f[c-k*v[i]]+k*w[i]);
            rest-=k;
            k+=k;
        }
        for(int c=m;c>=0;c--)
            if(c-rest*v[i]>0) f[c]=max(f[c],f[c-rest*v[i]]+rest*w[i]);
    }
}

最后输出 \(f[m]\) 即可。

  • 单调队列优化

Example3: 完全多重背包问题III AcWing6

有 \(N\) 种物品和一个容量是 \(M\) 的背包。

第 \(i\) 种物品最多有 \(s_i\) 件，每件体积是 \(v_i\)，价值是 \(w_i\)。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。 \(0<N\leq 1000\)，\(0<V\leq 20000\)，\(0<v_i,w_i,s_i\leq 20000\)。

和上题相比，数据范围又扩大了，显然二进制拆分这一方法也不能行了。

现在我们考虑写出 多重背包的状态转移，其中 \(j\) 为状态，\(k\) 为决策：

\[f[j]=\max_{1\leq k\leq S_i} {f[j-k\times V_i]+k\times W_i} \]

经过思考可以发现，相邻两个状态 \(j\) 和 \(j-1\) 所对应的决策候选集合没有重叠。

再进一步思考，可以发现，我们可以将所有的 状态 \(j\) 按照除以 \(V_i\) 的余数分组，

对每一组分开计算，根据背包问题的特点，阶段 \(i\) 发生变化时，状态不会相互转移。

观察 直接拆分法 的代码，根据上述结论，我们可以：

将枚举 \(j,k\) 的过程，改为枚举每一个余数 \(j\in[0,V_i)\)，以及倒叙循环 \(k= (M-j)/V_i \sim 0\)，

此时，状态就可以用 \(k\times V_i+j\) 表示，决策候选集和为 \(\{l\times V_i+j|k-S_i\leq l\leq k-1 \}\)，

状态转移方程可变为：

\[f[k\times V_i+j]=\max _{k-S_i\leq l\leq k-1} \{f[l\times V_i+j]+(k-l)\times W_i\} \]

此时，可以惊喜地发现，这个状态转移方程和 围栏 那道题的转移方程几乎一模一样，

就又可以迁移做法，处理方式和那道题一样。

（如果你直接来看 优化多重背包，而没看 优化线性DP 的话，还是先去看一看吧）

故得到如下处理单调队列方式：

  1. 检查队头的合法性，把大于 \(k-1\) 的决策点出队；
  2. 取队头为最优决策，更新 \(f[k\times V_i+j]\)；
  3. 把新决策 \(l=k-S_i-1\) 插入队尾，并判断决策单调性，排除无用决策。

时间复杂度为 \(O(NM)\)，可以通过本题。

for(int i=1;i<=n;i++)
{
    int v,w,s;
    scanf("%d%d%d",&v,&w,&s);
    for(int j=0;j<v;j++)
    {
        deque<int> q;
        for(int k=j;k<=m;k+=v)
        {
            if(!q.empty()&&q.front()+s*v<k) q.pop_front();
            while(!q.empty()&&f[i-1][q.back()]+(k-q.back())/v*w<=f[i-1][k])
                q.pop_back();
            q.push_back(k);
            if(!q.empty()) f[i][k]=f[i-1][q.front()]+(k-q.front())/v*w;
        }
    }
}

Tips: 由于STL有常数，本题被卡为 TLE，故还有一个手写队列版本：

for(int i=1;i<=n;i++)
{
    int v,w,s;
    scanf("%d%d%d",&v,&w,&s);
    for(int j=0;j<v;j++)
    {
        int hh=0,tt=-1;
        for(int k=j;k<=m;k+=v)
        {
            if(hh<=tt&&q[hh]+s*v<k) hh++;
            while(hh<=tt&&f[i-1][q[tt]]+(k-q[tt])/v*w<=f[i-1][k])
                tt--;
            q[++tt]=k;
            f[i][k]=f[i-1][q[hh]]+(k-q[hh])/v*w;
        }
    }
}

最后输出 \(f[m][n]\) 即可。

当然，可以像 01背包那样 将第一维状态优化掉。

不过由于单调队列的存在，不能够倒序枚举，就只能再开一个数组 \(g\) 存之前的 \(f\) 数组。

for(int i=1;i<=n;i++)
{
    int v,w,s;
    scanf("%d%d%d",&v,&w,&s);
    memcpy(g,f,sizeof g);
    for(int j=0;j<v;j++)
    {
        int hh=0,tt=-1;
        for(int k=j;k<=m;k+=v)
        {
            if(hh<=tt&&q[hh]+s*v<k) hh++;
            while(hh<=tt&&g[q[tt]]+(k-q[tt])/v*w<=g[k])
                tt--;
            q[++tt]=k;
            f[k]=g[q[hh]]+(k-q[hh])/v*w;
        }
    }
}

最后输出 \(f[m]\) 即可。

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/30513.html

赞 (0)
老牧童老牧童
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信