什么是单调队列

单调队列就是元素单调的队列,譬如一个队列中的元素为 1,2,3,4,5,6,单调递增,这就是一个单调队列。咱们先看一道单调队列的模板题:poj2823/洛谷 P1886
怎么维护单调队列呢?譬如维护一个单调递增的队列,就是要进入一个元素的时候,把队尾小于它的元素统统出队即可。而在例题中,我们还要记录每个元素在原来数组中的下标以确定是否可用,如果已经出了当前窗口,则出队。


代码:

void getmin(){//单调递增
    int he=1,ta=1,i;
    for(i=1;i<=n;i++){
        while(he<ta&&q[ta-1]>=a[i])ta--;
        q[ta]=a[i];bj[ta]=i;ta++;
        if(i>=m){
            while(he<ta&&bj[he]<=i-m)he++;
            printf("%d ",q[he]);
        }
    }
}
void getmax(){//单调递减
    int he=1,ta=1,i;
    for(i=1;i<=n;i++){
        while(he<ta&&q[ta-1]<=a[i])ta--;
        q[ta]=a[i];bj[ta]=i;ta++;
        if(i>=m){
            while(he<ta&&bj[he]<=i-m)he++;
            printf("%d ",q[he]);
        }
    }
}

单调队列优化动态规划

例题 1:洛谷 P1725 琪露诺

链接:走你╭(′▽`)╯
这题就当是单调队列入门啦。
大家都知道 $f[i]=max(f[j])+v[i] (i-r<=j<=i-l)$
直接这么 dp 肯定超时,那么我们可以把 $f[i-r]$到 $f[i-l]$这一段都扔到单调队列里,然后取队首即可
单调队列一定不能删除还有可能用到的元素,也不能添加暂时不会用的元素,所以我们要确保在用单调队列时,$i-l$加了进去,没有被其后的元素删掉,而其后的东西也没有加进去。
所以就有了代码中的写法
代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;
#define ll long long
ll read(){
    ll q=0,w=1;char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+(ll)(ch-'0'),ch=getchar();
    return q*w;
}
const int maxn=200005;
int n,l,r;
ll v[maxn],f[maxn],ans;
int bj[maxn];
int main()
{
    int i,j,ta=1,he=1;ll kl;
    n=read();l=read();r=read();
    for(i=0;i<=n;i++)v[i]=read();
    f[0]=v[0];
    for(i=l;i<=n;i++){
        while(he<ta&&f[bj[ta-1]]<=f[i-l])ta--;
        bj[ta]=i-l;ta++;
        while(he<ta&&bj[he]<i-r)he++;
        f[i]=f[bj[he]]+v[i];
        if(i>=n-r)ans=max(ans,f[i]);
    }
    printf("%lld",ans);
    return 0;
}

例题 2:UESSTC594 我要长高

链接:走你╭(′▽`)╯

这题充满了恶意啊……
容易想到用 $f[i][j]$表示第 $i$个儿子长 $j$这么高的时候的最小损失值 (x[i] 表示 i 儿子本来的身高,则:
$$f[i][j]=min(f[i-1][k] + abs(j-k)×c+ (x[i]-j)×(x[i]-j))$$
现在我们分类讨论一下,假如 $j>k$:
$$f[i][j]=min(f[i-1][k]+(j-k)×c+(x[i]-j)×(x[i]-j)$$
变形可得:$$f[i][j]=min((f[i-1][k]-k×c)+(j×c+(x[i]-j)×(x[i]-j)))$$
显然前面那一坨可以塞在一个单调队列里来求小于 j 的情况下的最优 k,具体怎么实现看代码吧。然后 $j<k$的情况也差不多:
$$f[i][j]=min((f[i-1][k]+k×c)+(-j×c+(x[i]-j)×(x[i]-j)))$$


得到了美妙的代码:

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
const int maxn=105;
int n,c,inf=0x3f3f3f3f;
int f[2][maxn],q[maxn];
int main()
{
    int x,i,j,t,ans,he,ta;
    while(scanf("%d%d",&n,&c)==2){
        x=read();t=1;
        for(i=0;i<x;i++)f[t][i]=inf;
        for(i=x;i<=100;i++)f[t][i]=(x-i)*(x-i);
        for(i=2;i<=n;i++){
            t=i&1;x=read();
            he=ta=1;
            for(j=0;j<=100;j++){//比前一个人高,显然弄到 j 的时候 k 取 0~j-1 的情况都已讨论过
                int kl=f[t^1][j]-j*c;
                while(he<ta&&q[ta-1]>=kl)ta--;
                q[ta]=kl;ta++;
                if(j<x)f[t][j]=inf;
                else f[t][j]=q[he]+j*c+(x-j)*(x-j);
            }
            he=ta=1;
            for(j=100;j>=0;j--){//比前一个人矮,显然弄到 j 的时候 k 取 j+1~100 的情况都已讨论过
                int kl=f[t^1][j]+j*c;
                while(he<ta&&q[ta-1]>=kl)ta--;
                q[ta]=kl;ta++;
                if(j<x)f[t][j]=inf;
                else f[t][j]=min(f[t][j],q[he]-j*c+(x-j)*(x-j));
            }
        }
        t=n&1;ans=inf;
        for(i=0;i<=100;i++)ans=min(ans,f[t][i]);
        printf("%d\n",ans);
    }
    return 0;
}

例题 3:HDU3401

链接:走你╭(′▽`)╯

题目大意是买股票,第 i 天买花 $ap[i]$元,卖得 $bp[i]$元,可以买 $as[i]$张或者卖 $bs[i]$张,两次交易之间必须间隔 $w$天,并且手上最多持有 $m$股,求最多赚多少钱。
$f[i][j]$表示第 i 天持有 j 股的最多收益,
如果不交易,那么 $f[i][j]=f[i-1][j]$
如果买 $f[i][j]=f[i-w-1][k]-(j-k)×ap[i]$
如果卖 $f[i][j]=f[i-w-1][k]+(k-j)×bp[i]$
(因为不交易的状态已经转移了,所以买和卖只要考虑第 $i-w-1$天即可)
然后我们把状态转移方程变形一下,就是
买:$f[i][j]=(f[i-w-1][k]+k×ap[i])-j×ap[i]$
卖:$f[i][j]=(f[i-w-1][k]+k×ab[i])-j×bp[i]$
前面那陀塞单调队列里,处理一下边界,然后就是考虑一下买的数量的问题即可。


#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=2005;
int T,n,m,w,ans,inf=0xfffffff;
int ap[N],bp[N],as[N],bs[N],f[N][N],q[N],bj[N];
int main()
{
    int i,j,he,ta,kl;
    T=read();
    while(T--){
        n=read();m=read();w=read();
        for(i=1;i<=n;i++)
            ap[i]=read(),bp[i]=read(),as[i]=read(),bs[i]=read();
        for(i=0;i<=n;i++)
            for(j=0;j<=m;j++)f[i][j]=-inf;
        for(i=1;i<=w+1;i++)
            for(j=0;j<=m&&j<=as[i];j++)f[i][j]=-j*ap[i];
        for(i=1;i<=n;i++){
            for(j=0;j<=m;j++)f[i][j]=max(f[i][j],f[i-1][j]);
            if(i<=w+1)continue;
            he=ta=1;
            for(j=0;j<=m;j++){//买
                kl=f[i-w-1][j]+j*ap[i];
                while(he<ta&&q[ta-1]<=kl)ta--;
                q[ta]=kl;bj[ta]=j;ta++;
                while(he<ta&&j-bj[he]>as[i])he++;
                f[i][j]=max(f[i][j],q[he]-j*ap[i]);
            }
            he=ta=1;
            for(j=m;j>=0;j--){//不买
                kl=f[i-w-1][j]+j*bp[i];
                while(he<ta&&q[ta-1]<=kl)ta--;
                q[ta]=kl;bj[ta]=j;ta++;
                while(he<ta&&bj[he]-j>bs[i])he++;
                f[i][j]=max(f[i][j],q[he]-j*bp[i]);
            }
        }
        ans=0;
        for(i=0;i<=m;i++)ans=max(ans,f[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}

例题 4:POJ1821

链接:走你╭(′▽`)╯

题目大意:你带着一群工人刷墙,第 i 个工人被 502 胶粘在了 s[i] 号位子上,他由于手臂长度,唯一的刷墙方式是大手一挥,将第 s[i] 格加上两边的格子共计 k 个刷好(0<=k<=l[i],刷了就必须刷 s[i] 格),然后他刷一格要 p[i] 元的工资。你现在想尽可能多的坑钱,但是反复刷一个格子太明显了是要不得的,求最多可以坑多少钱。
设 f[i][j] 表示前 i 个工人刷 j 个格子(显然工人已经按照站位排好序了),那么:
$$f[i][j]=max(f[i][j-1],f[i-1][j],f[i-1][k]+(j-k)×p[i])$$
分别表示第 j 面墙不刷,第 i 个工人自己玩儿去,和一个转移。
于是我们把后面的式子变形,有 k 的放在一块儿(肯定大家已经会变了吧,$f[i][j]=(f[i-1][k]-k×p[i])+j×p[i]$
不过边界值是很麻烦的,对于可以作为k的值,一定满足 $k<s[i]$,对于可以使用第3个方程的j值,一定满足 $j>=s[i]$


#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,m,ans;
struct node{int l,p,s;}t[105];
int f[105][16005],q[16055],bj[16055];
bool cmp(node a,node b){return a.s<b.s;}
int main()
{
    int i,j,he,ta,kl;
    m=read();n=read();
    for(i=1;i<=n;i++)t[i].l=read(),t[i].p=read(),t[i].s=read();
    sort(t+1,t+1+n,cmp);
    for(i=1;i<=n;i++){
        he=ta=1;
        for(j=0;j<=m;j++){
            if(j!=0)f[i][j]=max(f[i-1][j],f[i][j-1]);
            else f[i][j]=f[i-1][j];
            if(j>=t[i].s+t[i].l)continue;//有些木板不能涂色
            if(j<t[i].s){//符合条件的才可以入队!
                kl=f[i-1][j]-j*t[i].p;
                while(he<ta&&q[ta-1]<=kl)ta--;
                q[ta]=kl;bj[ta]=j;ta++;
                continue;//第 i 个人不能涂这些木块
            }
            while(he<ta&&j-bj[he]>t[i].l)he++;
            f[i][j]=max(f[i][j],q[he]+t[i].p*j);
        }
    }
    for(i=1;i<=m;i++)ans=max(ans,f[n][i]);
    printf("%d",ans);
    return 0;
}

总结

可以用单调队列优化的 dp 题在将方程变形后,有一段可以看做不含有当前状态 j,只含有前置状态 k 的一个整体,这个整体可以塞到单调队列里。

分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

2 条评论

NTFAKIOI · 2019年10月5日 4:30 下午

讲真,就讲题目,还是比较蒙啊~

彭书博 · 2017年6月22日 9:10 下午

%%%dalao%%%

发表回复

Avatar placeholder

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