單調隊列總結

  • 2020 年 7 月 30 日
  • 筆記

定義

單調隊列，即單調遞減或單調遞增的隊列。

入門題(洛谷P1886滑動窗口)

傳送門

題目描述

分析

如果用暴力求解的話，我們要將這一個長度為\(k\)的區間掃一遍
但是實際上，有很多值是顯然不會對答案產生貢獻的
比如我們要維護該區間的最大值，當前隊尾的的元素是\(4\)，下一個要加進去的元素是\(5\)
此時隊尾一定不會對答案產生貢獻，因為它的值比下一個元素小，而且當前值繼續對答案產生貢獻的時間也更短
這樣，我們就相當於維護了一個單調遞減的隊列
維護區間最小值同理

程式碼

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
ll a[maxn];
int q[maxn];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    int head=1,tail=0;
    for(int i=1;i<=n;i++){
        while(head<=tail && i-q[head]+1>k) head++;
        while(head<=tail && a[i]<a[q[tail]]) tail--;
        q[++tail]=i;
        if(i>=k)printf("%lld ",a[q[head]]);
    }
    printf("\n");
    head=1,tail=0;
    for(int i=1;i<=n;i++){
        while(head<=tail && i-q[head]+1>k) head++;
        while(head<=tail && a[i]>a[q[tail]]) tail--;
        q[++tail]=i;
        if(i>=k)printf("%lld ",a[q[head]]);
    }
    printf("\n");
    return 0;
}

其它題目

P2952 [USACO09OPEN]Cow Line S
P1440 求m區間內的最小值
P1638 逛畫展
P1901 發射站
P2032 掃描
P2947 [USACO09MAR]Look Up S
P1714 切蛋糕
P2629 好消息，壞消息

單調隊列優化DP

P2627 [USACO11OPEN]Mowing the Lawn G

題目描述

分析

暴力的\(DP\)方程比較好想，我們設\(f[i]\)為選擇到第\(i\)頭奶牛，並且第\(i\)頭奶牛必須選的最大價值
則\(f[i]=max(f[i],f[j]+sum[i]-sum[j+1])(i-(j+1)<=k)\)
我們只需要用單調隊列搞一下\(f[j]-sum[j+1]\)的最大值即可

程式碼

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
ll f[maxn],head,tail,sum[maxn],a[maxn];
int q[maxn];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
        if(i<=k) f[i]=sum[i];
    }
    ll ans=0;
    head=1,tail=1;
    for(int i=1;i<=n;i++){
        while(head<=tail && i-q[head]-1>k) head++;
        f[i]=max(f[i],f[q[head]]+sum[i]-sum[q[head]+1]);
        ans=max(ans,f[i]);
        while(head<=tail && f[i]-sum[i+1]>f[q[tail]]-sum[q[tail]+1]) tail--;
        q[++tail]=i;
    }
    printf("%lld\n",ans);
    return 0;
}

P1725 琪露諾

題目描述

分析

對於每一個給定的\(i\)，我們都可以從\([i-r,i-l]\)區間中選出一個最大的\(f\)值來更新
用一個單調遞減的隊列維護即可
注意隊列中存的是位置，而不是標號

程式碼

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int a[maxn],q[maxn],f[maxn];
int main(){
    for(int i=0;i<maxn;i++){
        f[i]=-0x3f3f3f3f;
    }
    int n,l,r;
    scanf("%d%d%d",&n,&l,&r);
    for(int i=0;i<=n;i++){
        scanf("%d",&a[i]);
    }
    f[0]=0;
    int head=1,tail=0,cnt=0;
    for(int i=l;i<=n;i++){
        while(head<=tail && f[q[tail]]<=f[i-l]) tail--;
        q[++tail]=i-l;
        while(q[head]+r<i) head++;
        f[i]=f[q[head]]+a[i];
    }
    int ans=-0x3f3f3f3f;
    for(int i=n-r+1;i<=n;i++){
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    return 0;
}

P3957 跳房子

題目描述

分析

這道題剛一看上去和上一道題一模一樣，但是隊列裡面存儲的不是位置而是標號
因此我們要用雙重循環來維護

程式碼

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,d,k;
int f[maxn],q[maxn],a[maxn],wz[maxn];
bool jud(int dd){
    for(int i=0;i<maxn;i++) f[i]=-0x3f3f3f3f;
    memset(q,0,sizeof(q));
    int tmin=max(1,d-dd),tmax=d+dd;
    int ans=0;
    int head=1,tail=0;
    f[0]=0;
    for(int i=1,j=0;i<=n;i++){
        while(wz[i]-wz[j]>=tmin && j<i){
            if(f[j]!=-0x3f3f3f3f){
                while(head<=tail && f[q[tail]]<=f[j]) tail--;
                q[++tail]=j;
            }
            j++;
        }
        while(head<=tail && wz[i]-wz[q[head]]>tmax) head++;
        if(head<=tail) f[i]=f[q[head]]+a[i];
        ans=max(ans,f[i]);
    }
    if(ans>=k) return 1;
    return 0;
}
int main(){
    scanf("%d%d%d",&n,&d,&k);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&wz[i],&a[i]);
    }
    int l=0,r=1e9,mids;
    while(l<=r){
        mids=(l+r)>>1;
        if(jud(mids)) r=mids-1;
        else l=mids+1;
    }
    if(l>1e9) printf("-1\n");
    else printf("%d\n",l);
    return 0;
}

其它題目

P2422 良好的感覺
P3572 [POI2014]PTA-Little Bird
P3800 Power收集
P3594 [POI2015]WIL-Wilcze doły

VirMach 便宜 VPS

QNews

QNews