单调队列优化 DP

2023-06-14

OI 知识>动态规划

4.9k words

单调队列优化 DP

前置知识：单调队列

一，概览

某些特定 DP，其当前状态的所有值都可以通过上一状态的某个连续段得到，要对这个连续段求区间最值，相邻状态的区间上下界单调变化。

对于这类动态规划问题，发现我们可以在状态转移当中引入单调队列，对 DP 进行优化。

二，思路

例题：最大子序和

给定一个长度为 \(N\) 的整数序列，从中找出一段长度不超过 \(M\) 的连续子序列，使得子序列中所有数的和最大。\(N,M\leq 3\times 10^5\)。

对于这道题，其答案可以形式化表示为：

\(ans=\) \(max_{1\leq i\leq N}\) \((sum[i]-\) \(min_{i-M\leq j\leq i-1}\) \(sum[j])\)

其中，\(i\) 类似于动态规划中的状态，\(j\) 类似于动态规划中的决策。我们从小到大枚举每个 \(i\in[1,N]\) 时，当 \(i\) 增大 \(1\) 时，\(j\) 的取值范围 \([i-M,i-1]\) 的上下界也同时增大 \(1\)，变为 \([i-M+1,i]\)。这意味着有一个新的决策 \(j=i\) 进入候选集和，同时 \(j=i-M\) 这一决策过时，需要从集合中删除。

经过分析发现此题取值范围上下界单调变化，每个决策在候选集和中最多被插入或删除一次，所求的是最值，可以使用单调队列优化。

首先求出每个元素的前缀和，建立前缀和数组。由于要求的是区间前缀和最小值，建立一个单调递增队列，以使队头为最小值，并保证了队头弹出后新队头为新的最小值。对于前缀和数组中的的每个数按一定规则依次插入，假设待插入元素下标为 \(i\)，值为 \(s[i]\)，则插入规则可表示如下：

若队头元素的下标 \(j\) 满足 \(j<i-M\)，弹出队头；
查询最优决策时队头即为所求；
当队尾元素的值 \(s[j]\) 足 \(s[j]>s[i]\) 时，弹出队尾直到队列为空或满足单调性；
插入新元素的下标。

对于第二条规则，由于 \(j\) 的取值最多到 \(i-1\)，故让 \(i\) 先入队再查询是不正确的，而应该先查询。

对于第三条规则，\(s[j]>s[i]\) 时，维护队列单调性。分析发现对于 \(i\) 之后的状态，取区间最小值时在 \(i\) 和 \(j\) 中选择 \(i\) 更优，\(j\) 不会再有贡献，所以将队尾 \(j\) 弹出直到队列单调是正确的。

对于第四条规则，在单调队列中仅需要插入下标即可，根据下标访问前缀和数组可得取值。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,a[300005];
deque<int> q;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
    q.push_back(0),ans=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        if(q.size()&&q.front()<i-m) q.pop_front();
        ans=max(ans,a[i]-a[q.front()]);
        while(q.size()&&a[q.back()]>=a[i]) q.pop_back();
        q.push_back(i);
    }
    cout<<ans<<endl;
}

三，单调队列优化多重背包

给出问题模型：

给定 \(N\) 种物品，其中第 \(i\) 种物品体积为 \(V_i\)，价值为 \(W_i\)，数量为 \(C_i\)。有一个容积为 \(M\) 的背包，要求选择若干物品放入背包，使得物品总体积不超过 \(M\) 的前提下价值之和最大

1. 回顾：多重背包的解法

① 朴素解法

把第 \(i\) 种物品看作独立的 \(C_i\) 件物品，转化为 \(\sum_{i=1}^N C_i\) 个物品的 \(0/1\) 背包。时间复杂度为 \(O(M\times \sum_{i=1}^N C_i)\)。

code

int c[maxn+5],v[maxn+5],w[maxn+5];
int f[maxm+5];
memset(f,0xc0,sizeof(f))   //-inf
f[0]=0;
for(int i=1;i<=n;i++)
    for(int j=1;j<=c[i];j++)
        for(int k=m;k>=v[i];k--)
            f[k]=max(f[k],f[k-v[i]]+w[i]);
int ans=0;
for(int i=0;i<=m;i++) ans=max(ans,f[i]);

② 二进制拆分法

在 \(2\) 的整数次幂中选取若干数相加，可以表示出任意整数，于是对于 \(C_i\)，将其二进制拆分为 \(2^0+\) \(2^1+\) \(2^2+...+\) \(2^p+R_i\)，\(R_i<2^{p+1}\)，这样便将 \(C_i\) 拆分为了 \(p+2\) 件物品，其体积与价值分别乘相应倍数后进行 \(0/1\) 背包即可，时间复杂度为 \(O(M\times \sum_{i=1}^N \log C_i)\)。

code

int c[maxn+5],v[maxn+5],w[maxn+5];
int t,val[maxN+5],wei[maxN+5]
int f[maxm+5];
memset(f,0xc0,sizeof(f))   //-inf
f[0]=0;
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=c[i];j<<=1)
        wei[++t]=v[i]*j,val[t]=w[i]*j,c[i]-=j;
    if(c[i]) wei[++t]=v[i]*c[i],val[t]=w[i]*c[i];
}
for(int i=1;i<=cnt;i++)
    for(int j=m;j>=wei[i];j--)
        f[j]=max(f[j],f[j-wei[i]]+val[i]);
int ans=0;
for(int i=0;i<=m;i++) ans=max(ans,f[i]);

2. 单调队列优化

若使用单调队列，时间复杂度可进一步降至 \(O(NM)\)。

当外层循环进行到 \(i\) 时，\(F[j]\) 表示从前 \(i\) 种物品中选若干放入背包使体积之和为 \(j\) 时，价值之和最大是多少。倒序循环 \(j\)，在状态转移时，第 \(i\) 种物品个数为 \(cnt\)，列出状态转移方程：

\(F[j]=\) \(max_{1\leq cnt\leq C_i}\) \((F[j-cnt\times V_i]+\) \(cnt\times\) \(W_i)\)

能够转移到 \(j\) 的候选集合为 \(\{j-cnt\times V_i|1\leq cnt\leq C_i\}\)。发现相邻状态 \(j\) 和 \(j-1\) 对应的候选集和没有重叠，很难由 \(j-1\) 对应的集合得到 \(j\) 对应的集合。但是对于 \(j\) 和 \(j-V_i\)，这两者对应的候选集和重合度较高，由 \(j-V_i\) 向 \(j\) 转移时，一个已有决策被排除，只有一个新决策加入候选集和，所以我们可以把状态 \(j\) 按除以 \(V_i\) 的余数分组，对每一组分别计算，不同组之间不会互相转移。

新的 DP 过程如下：

对于每个余数 \(u\in [0,V_i-1]\)，倒序循环 \(p\in [1,\lfloor(M-u)/V_i\rfloor]\)，则对应的状态 \(j\) 可表示为 \(j=u+p\times V_i\)。第 \(i\) 种物品有 \(C-i\) 个。故能转移到 \(j=u+p\times V_i\) 的候选集和就是 \(\{u+k\times V_i|p-C_i\leq k\leq p-1\}\)。写出新的状态转移方程：

\(F[u+p\times V_i]=\) \(max_{p-C_i\leq k\leq p-1}\) \((F[u+k\times V_i]+\) \((p-k)\times\) \(W_i)\)

把外层条件 \(i\) 和 \(u\) 看作定值，内层循环 \(p\) 减小 \(1\) 时，决策 \(k\) 的取值范围 \([p-C_i,p-1]\) 的上下界均单调减小。状态转移方程等号右侧的式子仍然可以分为两部分，仅包含变量 \(p\) 的 \(p\times W_i\) 和仅包含变量 \(k\) 的 \(F[u+k\times V_i]-k\times W_i\)。于是可以建立一个 \(k\) 单调递减，\(F[u+k\times V_i]-k\times W_i\) 也单调递减的队列维护候选集和，对于每个 \(p\)，执行单调队列有以下三个操作：

检查队头合法性，把大于 \(p-1\) 的决策出队。
取队头为最优策略
检查队尾单调性，弹出无用决策。
把决策 \(k=p-C_i-1\) 入队。

code：双端队列版（不推荐）

int calc(int i,int u,int k)
{
    return f[u+k*V[i]]-k*W[i];
}
int main()
{
    cin>>n>>m;
    memset(f,0x80,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int u=0;u<V[i];u++)
        {
            int maxn=(m-u)/V[i];
            for(int k=maxn-1;k>=max(maxn-C[i],0);k--)
            {
                while(!q.empty()&&calc(i,u,q.back())<=calc(i,u,k))
                    q.pop_back();
                q.push_back(k);
            }
            for(int p=maxn;p>=0;p--)
            {
                while(!q.empty()&&q.front()>p-1) q.pop_front();
                if(!q.empty())
                    f[u+p*V[i]]=max(f[u+p*V[i]],calc(i,u,q.front())+p*W[i]);
                if(p-C[i]-1>=0)
                {
                    while(!q.empty()&&calc(i,u,q.back())<=calc(i,u,p-C[i]-1))
                        q.pop_back();
                    q.push_back(p-C[i]-1);
                }
            }
        }
    }
}

code：数组版

#include<bits/stdc++.h>
using namespace std;
int n,m,v,w,c,mx,ans,f[40005];
int h,t,q[100005];
inline int rd()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void wt(int x)
{
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
int main()
{
    n=rd(),m=rd();
    for(int i=1;i<=n;i++)
    {
        v=rd(),w=rd(),c=rd();
        for(int u=0;u<w;u++)
        {
            h=1,t=0,mx=(m-u)/w;
            for(int k=mx-1;k>=max(mx-c,0);k--)
            {
                while(h<=t&&f[u+q[t]*w]<=f[u+k*w]+(q[t]-k)*v) t--;
                q[++t]=k;
            }
            for(int p=mx;p>=0;p--)
            {
                while(h<=t&&q[h]>p-1) h++;
                if(h<=t) f[u+p*w]=max(f[u+p*w],f[u+q[h]*w]+(p-q[h])*v);
                if(p-c-1<0) continue;
                while(h<=t&&f[u+q[t]*w]<=f[u+(p-c-1)*w]+(q[t]-(p-c-1))*v) t--;
                q[++t]=p-c-1;
            }
        }
    }
    for(int i=1;i<=m;i++) ans=max(ans,f[i]);
    wt(ans);
    return 0;
}

四，总结

对于可以使用单调队列优化的题目，可以总结出如下通式：

\(F[i]=\) \(min_{L(i)\leq j\leq R(i)}\) \((F[j]+\) \(val(i,j))\)

其中 \(val(i,j)\) 可分为两部分，一部分仅与 \(i\) 有关，另一部分仅与 \(j\) 有关。

对于每个 \(i\)，无论采取哪个 \(j\) 作为决策，与 \(i\) 有关的部分都是相等的，而当 \(i\) 变化时，与 \(j\) 有关的部分不会发生变化，从而原来较优的决策在 \(i\) 改变后仍较优。

于是我们就可以使用单调队列维护第二部分单调性。

至于这一通式，在之后的学习中还会遇到。

五，习题

洛谷P1776 宝物筛选

套用多重背包板子即可。推荐使用二进制拆分（好写）或数组队列（较快）。

code：双端队列

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,v[100005],w[100005],c[100005],f[40005];
deque<int> q;
int calc(int i,int u,int k)
{
    return f[u+k*w[i]]-k*v[i];
}
inline int rd()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void wt(int x)
{
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
int main()
{
    n=rd(),m=rd();
    for(int i=1;i<=n;i++)
    {
        v[i]=rd(),w[i]=rd(),c[i]=rd();
        if(w[i]==0) {ans+=w[i]*c[i];continue;}
        for(int u=0;u<w[i];u++)
        {
            int mx=(m-u)/w[i];
            for(int k=mx-1;k>=max(mx-c[i],0);k--)
            {
                while(!q.empty()&&calc(i,u,q.back())<=calc(i,u,k))
                    q.pop_back();
                q.push_back(k);
            }
            for(int p=mx;p>=0;p--)
            {
                while(!q.empty()&&q.front()>p-1) q.pop_front();
                if(!q.empty())
                    f[u+p*w[i]]=max(f[u+p*w[i]],calc(i,u,q.front())+p*v[i]);
                if(p-c[i]-1>=0)
                {
                    while(!q.empty()&&calc(i,u,q.back())<=calc(i,u,p-c[i]-1))
                        q.pop_back();
                    q.push_back(p-c[i]-1);
                }
            }
        }
    }
    for(int i=1;i<=m;i++) ans=max(ans,f[i]);
    wt(ans);
    return 0;
}

code：数组队列

#include<bits/stdc++.h>
using namespace std;
int n,m,v,w,c,mx,ans,f[40005];
int h,t,q[100005];
inline int rd()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void wt(int x)
{
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
int main()
{
    n=rd(),m=rd();
    for(int i=1;i<=n;i++)
    {
        v=rd(),w=rd(),c=rd();
        for(int u=0;u<w;u++)
        {
            h=1,t=0,mx=(m-u)/w;
            for(int k=mx-1;k>=max(mx-c,0);k--)
            {
                while(h<=t&&f[u+q[t]*w]<=f[u+k*w]+(q[t]-k)*v) t--;
                q[++t]=k;
            }
            for(int p=mx;p>=0;p--)
            {
                while(h<=t&&q[h]>p-1) h++;
                if(h<=t) f[u+p*w]=max(f[u+p*w],f[u+q[h]*w]+(p-q[h])*v);
                if(p-c-1<0) continue;
                while(h<=t&&f[u+q[t]*w]<=f[u+(p-c-1)*w]+(q[t]-(p-c-1))*v) t--;
                q[++t]=p-c-1;
            }
        }
    }
    for(int i=1;i<=m;i++) ans=max(ans,f[i]);
    wt(ans);
    return 0;
}

code：二进制拆分

#include<bits/stdc++.h>
using namespace std;
int N,W,val,wei,num;
int v[2000000],w[2000000],f[2000000];
int cnt;
inline int rd()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int main()
{
    N=rd(),W=rd();
    for(int i=1;i<=N;i++)
    {
        val=rd(),wei=rd(),num=rd();
        for(int j=1;j<=num;j<<=1)
            v[++cnt]=val*j,w[cnt]=wei*j,num-=j;
        if(num)
            v[++cnt]=val*num,w[cnt]=wei*num;
    }
    for(int i=1;i<=cnt;i++)
        for(int j=W;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    cout<<f[W];
    return 0;
}

洛谷P2254 瑰丽华尔兹

\(O(NMK)\) 做法：设 \(f[i][j][k]\) 代表第 \(i\) 个时间段结束时到达 \((j,k)\) 的最长滑行距离，初始为负无穷，起点为 \(0\)。对于每一次询问，给出 \(s,t\) 之后可以得到最大滑行长度，之后按方向遍历每一行（列），运用单调队列滑动窗口优化，可以在 \(O(NM)\) 时间复杂度得到一次移动后的 DP 数组，总共 \(K\) 次询问，总复杂度 \(O(NMK)\)。

code

#include<bits/stdc++.h>
using namespace std;
int const D[2][6]={{0,-1,1,0,0},{0,0,0,-1,1}};
char mp[205][205];
int n,m,x,y,k,s,t,d,mx,ans,f[205][205];
struct que {int dp,len;} q[205];
void solve(int x,int y,int mx,int d)
{
    int h=1,t=0,l=1;
    for(;x>=0&&x<n&&y>=0&&y<m;x+=D[0][d],y+=D[1][d],l++)
    {
        if(mp[x][y]=='x') {h=1,t=0;continue;}
        while(h<=t&&q[t].dp+l-q[t].len<f[x][y]) t--;
        q[++t]={f[x][y],l};
        if(h<=t&&q[t].len-q[h].len>mx) h++;
        f[x][y]=q[h].dp+l-q[h].len,ans=max(ans,f[x][y]);
    }
}
inline int rd()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void wt(int x)
{
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
signed main()
{
    n=rd(),m=rd(),x=rd()-1,y=rd()-1,k=rd();
    for(int i=0;i<n;i++) scanf("%s",mp[i]);
    memset(f,-1,sizeof(f)),f[x][y]=0;
    for(int i=1;i<=k;i++)
    {
        s=rd(),t=rd(),d=rd(),mx=t-s+1;
        if(d==1) for(int j=0;j<m;j++) solve(n-1,j,mx,d);
        if(d==2) for(int j=0;j<m;j++) solve(0,j,mx,d);
        if(d==3) for(int j=0;j<n;j++) solve(j,m-1,mx,d);
        if(d==4) for(int j=0;j<n;j++) solve(j,0,mx,d);
    }
    wt(ans);
    return 0;
}

洛谷P2569 股票交易

\(O(T·MaxP)\) 做法：设 \(f[i][j]\) 代表第 \(i\) 天结束时持有 \(j\) 股时收益最大值，第 \(0\) 天初始负无穷，\(f[0][0]=0\)。之后考虑转移，对于每一天有如下三种情况： 1. 可以不进行交易，此时 \(f[i][j]=f[i-1][j]\)； 2. 可以买入，此时第 \(i\) 天的结果将由第 \(\max(i-w-1,0)\) 天转移得到，以 \(as\) 为滑动窗口大小，引入单调队列优化进行转移。 3. 可以卖出，同样由第 \(\max(i-w-1,0)\) 天转移得到，以 \(bs\) 为窗口大小单调队列优化。

需要注意，买入时持有 \(j\) 股的状态只能由比 \(j\) 小的状态得到，所以正序枚举 \(j\)，类似的，卖出时持有 \(j\) 股的状态只能由比 \(j\) 大的状态得到，所以倒序枚举 \(j\)。

显然转移到最后一天时，若手中有股票，全部卖出会得到更优解，于是答案取 \(f[T][0]\)。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,w,ap,bp,as,bs,lst,h,t,f[2005][2005],q[2005];
inline int rd()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void wt(int x)
{
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
int main()
{
    n=rd(),m=rd(),w=rd();
    for(int i=1;i<=m;i++) f[0][i]=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        ap=rd(),bp=rd(),as=rd(),bs=rd();
        for(int j=0;j<=m;j++) f[i][j]=f[i-1][j];
        lst=max(i-w-1,0),h=1,t=0;
        for(int j=0;j<=m;j++)
        {
            while(h<=t&&q[h]<j-as) h++;
            while(h<=t&&f[lst][q[t]]+(q[t]-j)*ap<f[lst][j]) t--;
            q[++t]=j,f[i][j]=max(f[i][j],f[lst][q[h]]+(q[h]-j)*ap);
        }
        h=1,t=0;
        for(int j=m;j>=0;j--)
        {
            while(h<=t&&q[h]>j+bs) h++;
            while(h<=t&&f[lst][q[t]]+(q[t]-j)*bp<f[lst][j]) t--;
            q[++t]=j,f[i][j]=max(f[i][j],f[lst][q[h]]+(q[h]-j)*bp);
        }
    }
    cout<<f[n][0]<<endl;
    return 0;
}

洛谷P3572 PTA-Little Bird

\(O(qn)\) 做法：设 \(f[i]\) 代表一只鸟飞到第 \(i\) 棵树的最小疲劳值，初始为正无穷，\(f[1]=0\)。\(f[i]\) 可以由 \(f[i-k]\) 到 \(f[i-1]\) 转移而来，于是引入单调队列优化 DP。建立一个单调递增队列维护，队头为疲劳值最小值，但注意到转移还与树的高度有关，应是队头元素的高度最大以使转移中尽量不增加疲劳值。由于转移中疲劳值至多增加一，故取疲劳值低的转移一定不劣于取疲劳值高的转移，故单调队列应以疲劳值为第一关键字单调递减，相同疲劳值以树高为第二关键字比较，在队列中保留树高较高的即可。答案取 \(f[n]\)。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,k,h,t,d[1000005],f[1000005],q[1000005];
inline int rd()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void wt(int x)
{
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
signed main()
{
    n=rd();
    for(int i=1;i<=n;i++) d[i]=rd();
    m=rd();
    for(int i=1;i<=m;i++)
    {
        k=rd(),h=1,t=1,q[1]=1;
        memset(f,0x3f,sizeof(f)),f[1]=0;
        for(int j=2;j<=n;j++)
        {
            while(h<=t&&q[h]<j-k) h++;
            f[j]=f[q[h]]+(d[q[h]]<=d[j]);
            while(h<=t&&(f[q[t]]==f[j]?d[j]>d[q[t]]:f[j]<f[q[t]])) t--;
            q[++t]=j;
        }
        wt(f[n]),putchar('\n');
    }
    return 0;
}

洛谷P3594 WIL

\(O(n)\) 做法：题意就是找一段大区间，其中间一段不长于 \(d\) 的小区间内所有数变 \(0\) 后大区间内所有数的和不大于 \(p\)，求大区间最长长度。首先有一个显然结论就是变 \(0\) 的点越多，答案越优，也就是说必然有 \(d\) 个点变 \(0\)。此外还有大区间某端点一定时，变 \(0\) 的小区间原值和越大，答案越优，因为删去的值增大，大区间的另一端点只可能更远离定端点，此时大区间只可能更大。

接下来考虑 DP，从 \(d\) 开始枚举大区间右端点 \(i\)，大区间左端点初始为 \(1\)，引入单调递减队列维护变 \(0\) 区间的原值和最大值，队列中存小区间左端点。

首先在保证单调性前提下将以 \(i\) 为右端点的小区间的左端点入队。之后比较大区间删去 \(sum[q[h]+d-1]-\) \(sum[q[h]-1]\) 后的数值和与 \(p\) 的关系，若大于 \(p\)，则大区间左端点 \(l\) 需右移，注意右移 \(l\) 时还要检查小区间是否包含在大区间内，若不在，更新小区间。

最终答案即为 \(\max_{r=d}^n(r-l+1)\)

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,p,d,h,t,l,ans,w[2000005],q[2000005];
inline int rd()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void wt(int x)
{
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
signed main()
{
    n=rd(),p=rd(),d=rd();
    for(int i=1;i<=n;i++) w[i]=rd(),w[i]+=w[i-1];
    ans=d,l=1,h=1,t=0;
    for(int i=d;i<=n;i++)
    {
        while(h<=t&&w[q[t]+d-1]-w[q[t]-1]<=w[i]-w[i-d]) t--;
        q[++t]=i-d+1;
        if(i-l+1>d&&w[i]-w[l-1]-w[q[h]+d-1]+w[q[h]-1]>p)
            {l++;if(h<=t&&q[h]<l) h++;}
        ans=max(ans,i-l+1);
    }
    wt(ans);
    return 0;
}

Categories

Tags

Archives

Recent Posts

单调队列优化 DP

单调队列优化 DP

一，概览

二，思路

三，单调队列优化多重背包

1. 回顾：多重背包的解法

① 朴素解法

② 二进制拆分法

2. 单调队列优化

四，总结

五，习题

洛谷P1776 宝物筛选

洛谷P2254 瑰丽华尔兹

洛谷P2569 股票交易

洛谷P3572 PTA-Little Bird

洛谷P3594 WIL