Processing math: 100%

【算法】单调队列优化动态规划—litble

于由litble发布

什么是单调队列

单调队列就是元素单调的队列，譬如一个队列中的元素为 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]);
        }
    }
}
C++
Copy

单调队列优化动态规划

例题 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;
}
C++
Copy

例题 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;
}
C++
Copy

例题 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;
}
C++
Copy

例题 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;
}
C++
Copy

总结

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

分类： 文章

litble

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

2 条评论

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

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

回复

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

%%%dalao%%%

回复

发表回复

Avatar placeholder

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