05 单调队列优化DP：华科A题

2024-08-17 算法►动态规划►DP的单调队列优化 DP的单调队列优化, 动态规划, 算法 0 评论

单调队列

“如果一个选手比你小还比你强，你就可以退役了。”——单调队列的原理

单调队列是一种主要用于解决”滑动区间“的最值问题的数据结构

即，在长度为的序列中，求每个长度为的区间的区间最值。它的时间复杂度是，在这个问题中比的ST表和线段树要优。

单调队列的基本思想是，维护一个双向队列（deque），遍历序列，仅当一个元素可能成为某个区间最值时才保留它。

形象地打个比方，上面的序列可以看成学校里各个年级XCPC选手，数字越大代表能力越强。每个选手只能在大学四年间参赛，毕业了就没有机会了。那么，每一年的王牌选手都在哪个年级呢？

一开始的时候，大三大四的学长都比较菜，大二的最强，而大一的等大二的毕业后还有机会上位，所以队列里有两个数。

一年过去了，原本大一的成为大二，却发现新进校的新生非常强，自己再也没有机会成为最大值了，所以弹出队列。

又过了一年，新入校的新生尽管能力只有1，但理论上只要后面的人比他还菜，还是可能成为区间最大值的，所以入队。

终于，原本的王牌毕业了，后面的人以为熬出头了，谁知道这时一个巨佬级别的新生进入了集训队，这下其他所有人都没机会了。

（这只是比方，现实中各位选手的实力是会增长的，不符合这个模型ovo）

总之，观察就会发现，我们维护的这个队列总是单调递减的。如果维护区间最小值，那么维护的队列就是单调递增的。这就是为什么叫单调队列。

例题：单调队列优化动态规划的应用

选择数字

题目描述

给定一行 $n$ 个非负整数 $a_1 \cdots a_n$ 。现在你可以选择其中若干个数，但不能有超过 $k$ 个连续的数字被选择。你的任务是使得选出的数字的和最大。

输入格式

第一行两个整数 $n$ ， $k$ 。

以下 $n$ 行，每行一个整数表示 $a_i$ 。

输出格式

输出一个值表示答案。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $20\%$ 的数据， $n \le 10$ 。

对于另外 $20\%$ 的数据， $k=1$ 。

对于 $60\%$ 的数据， $n \le 1000$ 。

对于 $100\%$ 的数据， $1 \le n \le 100000$ ， $1 \le k \le n$ ， $0 \le$ 数字大小 $\le 1,000,000,000$ 。

时间限制 $500$ ms。

这种题是很典型的单调队列优化DP。

我们把问题转化为删除若干个数，且删除的数间隔不超过k，求删除数的最小值。设dp[i]表示在删除第i个数的情况下，前i个数中删除数的最小和。那么很容易想到转移方程：

这是因为，如果要删除某个数，除非它是前 k+1个数之一，否则在它之前的k+1个数中，至少要删除一个。最后的答案在最后 k+1个数里找最小值，然后用总和去减即可，因为最后 k+1个数中至少有一个是要删除的。

这个朴素方法是O（mn）的，为了优化它，我们可以使用单调队列。注意到，我们不断地在求dp的区间最小值，而且区间长度是固定的m+1 ，这正好符合滑动窗口的模型。只不过，我们需要动态地进行整个过程，即，在维护单调队列的过程中求出dp。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxsize = 100005;
int dp[maxsize] = {0};
deque<int> q;
signed main()
{
    int n,k,a[maxsize],sum=0;
    cin>>n>>k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum+=a[i];
    }

    //看作删除若干个数，但是不能有间隔超过k；
    //dp[i]表示，删除a[i]的情况下，完成删除的最小值
    for(int i=1;i<=n;i++)
    {
        if(i<=k+1)
            dp[i]=a[i];
        else 
            dp[i]=dp[q.front()]+a[i];        
        if(!q.empty() && q.front()<i-k) q.pop_front();
        while (!q.empty() && dp[q.back()] > dp[i])
        {
            q.pop_back();
        }
        q.push_back(i);
    }
    int emin=LONG_LONG_MAX;
    for(int i=n-k;i<=n;i++)
    {
        emin=min(dp[i],emin);
    }
    cout<<sum-emin<<endl;
}

注意，在这个过程中的易错点是：

进入队列的是元素下标不是元素内容！！，且每一次循环不一定一定有元素从头部出队。

另一个例题：华中科技大学2023新生赛A题

[HUSTFC 2023] 简单的加法乘法计算题

题目描述

JokerShaco 有一个数字 $x$ ，最开始 $x=0$ ，他想要把 $x$ 变成 $y$ 。为了达到这个目标，他可以利用两个集合 $A$ 和 $B$ 。其中集合 $A$ 包含 $n$ 个元素，分别是从 $1$ 到 $n$ 的所有正整数；集合 $B$ 包含 $m$ 个元素。每次它可以对 $x$ 进行如下任意次操作：

选择 $A$ 中的一个元素 $a$ ，令 $x$ 加上 $a$ 。
选择 $B$ 中的一个元素 $b$ ，令 $x$ 乘以 $b$ 。

已知 $y$ ， $n$ ， $m$ 和 $B$ 中 $m$ 个元素的具体值，JokerShaco 想知道让 $x$ 变成 $y$ 的最少操作次数。

输入格式

第一行包含三个整数 $y\ (1\le y\le 5\cdot 10^6)$ ， $n\ (1\le n\le 5\cdot 10^6)$ 和 $m\ (1\le m\le 10)$ ，其含义如题目所述。

第二行包含 $m$ 个正整数，其中第 $i$ 个表示 $B$ 中的第 $i$ 个元素 $b_i\ (1\le b_i\le 5\cdot 10^6)$ 。

输出格式

输出一个整数，表示让 $x$ 变成 $y$ 的最少操作次数。在题目条件下可知一定能将 $x$ 变成 $y$ 。

样例 #1

样例输入 #1

1
2

10 3 1
2

样例输出 #1

样例 #2

样例输入 #2

1 2	100 6 3 2 3 5

样例输出 #2

初步想法是利用线性动态规划进行，dp[i]表示y=i的时候需要走的最少步骤数，状态转移方程为：

dp[i]=min( minE(k from i-1 to i-n) {dp[k]+1} ,

minE(r from 1 to m) if(dp[i]%b[r]=0）dp[i]/b[r] )

可行代码：

#include <bits/stdc++.h>
using namespace std;
const int maxsize=5000005;
int dp[maxsize]={0};
deque <int> dq;
signed main()
{
    long long b[11];
    long long y,n,m;

    cin>>y>>n>>m;
    for(long long i=1;i<=m;i++)
    {
        cin>>b[i];
    }
    for(int j=1;j<maxsize;j++)
        {
            dp[j]=INT_MAX;
        }

    for (long long i = 1; i <= y; i++)
    {
        if(i<=n)
        {
            dp[i]=1;
        }
        else 
        {
            dp[i]=min(dp[i],dp[dq.front()]+1);
            for (long long r = 1; r <= m; r++)
            {
                 if (i % b[r] == 0)
                {
                   dp[i] = min(dp[i], dp[i / b[r]] + 1);
                }
            }
        }
        if(!dq.empty() && dq.front()<=i-n)
        {
            dq.pop_front();
        }
        while(!dq.empty() && dp[dq.back()]>dp[i])
        {
            dq.pop_back();
        }
        dq.push_back(i);//注意队列中始终是位置，而不是元素内容
    }

    cout<<dp[y]<<endl;

}

特定类型的题型：多重背包的单调队列优化

宝物筛选

题目描述

终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。

这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。

小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为 $W$ 的采集车，洞穴里总共有 $n$ 种宝物，每种宝物的价值为 $v_i$ ，重量为 $w_i$ ，每种宝物有 $m_i$ 件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

输入格式

第一行为一个整数 $n$ 和 $W$ ，分别表示宝物种数和采集车的最大载重。

接下来 $n$ 行每行三个整数 $v_i,w_i,m_i$ 。

输出格式

输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $30\%$ 的数据， $n\leq \sum m_i\leq 10^4$ ， $0\le W\leq 10^3$ 。

对于 $100\%$ 的数据， $n\leq \sum m_i \leq 10^5$ ， $0\le W\leq 4\times 10^4$ ， $1\leq n\le 100$ 。

多重背包的原始状态转移方程：

f(i,j)=max(f(i−1,j),f(i−1,j−v)+w,⋯,f(i−1,j−sv)+sw)

f(i,j−v)=max(f(i−1,j−v),f(i−1,j−2v)+w,⋯,f(i−1,j−(s+1)v)+(s)w)

f(i,j−2v)=max(f(i−1,j−2v),f(i−1,j−3v)+w,⋯,f(i−1,j−(s+2)v)+sw)

…

此处我们取 r = j % v

f(i,r+sv)=max(f(i−1,r+sv),f(i−1,r+(s−1)v)+w,⋯,f(i−1,r)+sw)

⋯

f(i,r+2v)=max(f(i−1,r+2v),f(i−1,r+v)+w,f(i−1,r)+2w)

f(i,r+v)=max(f(i−1,r+v),f(i−1,r)+w)

f(i,r)=f(i−1,r)

朴素二维数组代码：

#include <bits/stdc++.h>
using namespace std;
const int maxsize=4e2+5;
int dp[maxsize][maxsize]={0};
int v[105],w[105],m[105],n,W;
signed main()
{
    
    cin>>n>>W;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i]>>m[i];
    }
    for(int i=1;i<=n;i++)//当前考虑到第i件物品
    {
        for(int r=0;r<w[i];r++)//考虑余数r，余数可能为0~w[i]-1中的任意一个数字
        {
            deque<int> q;
            for(int j=r;j<=W;j+=w[i])
            {
                while(!q.empty() && j-q.front()>m[i]*w[i])
                    q.pop_front();
                while (!q.empty() && dp[i - 1][q.back()] + (j - q.back()) / w[i] * v[i] <= dp[i - 1][j])
                    q.pop_back();
                q.push_back(j);
                dp[i][j] = dp[i - 1][q.front()] + (j - q.front()) / w[i] * v[i];
            }
        }
    }
    cout<<dp[n][W]<<endl;

    return 0;
    

}

一维数组空间优化代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxsize=4e4+5;
int dp[maxsize]={0},g[maxsize]={0};
int v[10005],w[10005],m[10005],n,W;
signed main()
{
    
    cin>>n>>W;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i]>>m[i];
    }
    for(int i=1;i<=n;i++)//当前考虑到第i件物品
    {
        for(int r=0;r<w[i];r++)//考虑余数r，余数可能为0~w[i]-1中的任意一个数字
        {
            deque<int> q;
            memcpy(g,dp,sizeof(dp));
            for(int j=r;j<=W;j+=w[i])
            {
                while(!q.empty() && j-q.front()>m[i]*w[i])
                    q.pop_front();
                while (!q.empty() && g[q.back()] + (j - q.back()) / w[i] * v[i] <= g[j])
                    q.pop_back();
                q.push_back(j);
                dp[j] = g[q.front()] + (j - q.front()) / w[i] * v[i];
            }
        }
    }
    cout<<dp[W]<<endl;

    return 0;
    

}

本文链接： https://xqc-1368.github.io/2024/08/17/05 单调队列优化DP：华科A题/

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！

XQC-1368我见青山多妩媚料青山见我应如是

Harbin Institute of Technology, Shenzhen 计算机科学与技术本科在读

05 单调队列优化DP：华科A题

单调队列

单调队列是一种主要用于解决”滑动区间“的最值问题的数据结构

选择数字

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

[HUSTFC 2023] 简单的加法乘法计算题

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

特定类型的题型：多重背包的单调队列优化

宝物筛选

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

多重背包的原始状态转移方程：

XQC-1368我见青山多妩媚 料青山见我应如是

XQC-1368我见青山多妩媚料青山见我应如是