前置：

队列的定义

队列 是仅限在 一端 进行 插入，另一端 进行 删除 的 线性表。

队列 又被称为 先进先出 （First In First Out） 的线性表，简称 FIFO 队列。

队首

允许进行元素删除的一端称为 队首。

队尾

允许进行元素插入的一端称为 队尾。

数据入队

队列的插入操作，叫做 入队。它是将 数据元素 从 队尾 进行插入的过程

数据出队

队列的删除操作，叫做 出队。它是将 队首 元素进行删除的过程

清空队列

队列的清空操作，就是一直 出队，直到队列为空的过程，当 队首 和 队尾 重合时，就代表队尾为空了

获取队首数据

对于一个队列来说只能获取 队首 数据

双端队列的定义

双端队列 是一种具有 队列 和 栈 的性质的数据结构，是我们常说的 deque（double-ended queue），是一种限定 插入 和 删除 操作在表的两端进行的线性表。这两端分别被称为 队首 和 队尾。

队首入队

队列的插入操作，叫做 入队。

队首入队 就是将 数据元素 从 队首 进行插入的过程。

队尾入队

队尾入队 就是将 数据元素 从 队尾 进行插入的过程。

队首出队

队列的删除操作，叫做 出队。队首出队 是将 队首 元素进行删除的过程。

队尾出队

队尾出队 是将 队尾 元素进行删除的过程

单调队列

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

单调队列是一种主要用于解决滑动窗口类问题的数据结构，即，在长度为 n 的序列中，求每个长度为 m 的区间的区间最值。它的时间复杂度是 O(n) .

代码：

求区间最大值

1
2
3
4
5
6
7
8
9
10
11
deque<int> Q; // 存储的是编号
for (int i = 0; i < n; ++i)
{
    if (!Q.empty() && i - Q.front() >= m) 
        Q.pop_front();
    while (!Q.empty() && V[Q.back()] < V[i]) 
        Q.pop_back();
    Q.push_back(i); 
    if (i >= m - 1)
        cout << V[Q.front()] << " ";
}

滑动窗口 /【模板】单调队列

题目描述

有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如，对于序列 \([1,3,-1,-3,5,3,6,7]\) 以及 \(k = 3\)，有如下过程：

\[\def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array} \]

输入格式

输入一共有两行，第一行有两个正整数 \(n,k\)。 第二行 \(n\) 个整数，表示序列 \(a\)

输出格式

输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

样例 #1

样例输入 #1

1
2
8 3
1 3 -1 -3 5 3 6 7

样例输出 #1

1
2
-1 -3 -3 -3 3 3
3 3 5 5 6 7

提示

【数据范围】
对于 \(50\%\) 的数据，\(1 \le n \le 10^5\)；
对于 \(100\%\) 的数据，\(1\le k \le n \le 10^6\)，\(a_i \in [-2^{31},2^{31})\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
const int N = 1e7;
int a[N];
int q[N];
int q2[N];
int main()
{
int n,m;
cin>>n>>m;
rep(i,1,n)
{
    cin>>a[i];
}
int h=1,t=0;
rep(i,1,n)
{

while (h <= t && q[h] + m <= i)
{
    h++;
}
while (h <= t && a[i]<a[q[t]])
{
    t--;
}
q[++t] = i;
if(i>=m)
{
    cout<<a[q[h]]<<' ';
}
}
cout<<'\n';
 h = 1, t = 0;
rep(i, 1, n)
{

    while (h <= t && q2[h] + m <= i)
    {
        h++;
    }
    while (h <= t && a[i] > a[q2[t]])
    {
        t--;
    }
    q2[++t] = i;
    if (i >= m)
    {
        cout << a[q2[h]] << ' ';
    }
}
}

单调队列优化dp

当我们为了实现给动态规划的复杂度降维的时候，通常就需要单调栈/队列，通常用来维护前面状态下可以取到的最大值或者最小值，然后直接进行转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using namespace std;
const int N=1e7;
int a[N];
int f[N];
int que[N];
int h=0;
int t=0;
const int INF = 2e9;
int ans = -INF;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,l,r;
    cin>>n>>l>>r;
    memset(f, 128, sizeof(f));
    f[0]=0;
    rep(i,0,n)
    {
        cin>>a[i];
    }
    rep(i,l,n)
    {
        while (que[h] + r < i && t >= h)
        {
            h++;
        }
        while(f[i-l]>f[que[t]]&&t>=h)
        {
            t--;
        }
        que[++t]=i-l;
        f[i]=f[que[h]]+a[i];
        if(i+r>n)
        {
            ans=max(ans,f[i]);
        }
    }
cout<<ans;
}

对于常规多重背包，f[i][j]代表体积为j,选到第i个物品的最大价值。由于一种物体数量可以多个，故需要枚举数量。

1
f[i][j]=max( f[i-1] [j-k*v[i]] +k*w[i] ) 其中0<=k<=cnt[i]

其实是有二进制拆分做法的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for(int i=1;i<=n;i++)
{
	for(int j=1;j<=num[i];j<<=1)
    //二进制每一位枚举.
    //注意要从小到大拆分
	{
		num[i]-=j;//减去拆分出来的
		new_c[++tot]=j*c[i];//合成一个大的物品的体积
		new_w[tot]=j*w[i];//合成一个大的物品的价值
	}
	if(num[i])//判断是否会有余下的部分.
    //就好像我们某一件物品为13,显然拆成二进制为1,2,4.
    //我们余出来的部分为6,所以需要再来一份.
	{
		new_c[++tot]=num[i]*c[i];
		new_w[tot]=num[i]*w[i];
		num[i]=0;
	}
}

但今天的主题是单调队列

接下来开始进行推导过程

由：

1
f[i][j]=max( f[i-1] [j-k*v[i]] +k*w[i] ) 其中0<=k<=cnt[i]

cnt[i]代表这一种物体数目，w[i]是价值(wealth), v[i]是体积

我们设 j=k1*v[i] +d , k1=j/v[i] ,d=j%v[i] 前者是j能装下的最大个数，后者是余数

1
f[i][j]= max( f[i-1][ k1*v[i]+d -k*v[i]] + k*w[i] )   0<=k<=cnt[i]

把j代换成了 k1*w[i] +d

1
f[i][j]= max( f[i-1][ (k1-k)* v[i]+d] -(k1 -k) *w[i] ) + k1*w[i]  0<=k<=cnt[i]

0<=k<=cnt[i]

令(k1-k)-->k

1
f[i][j]= max( f[i-1][ k* v[i]+d] -k *w[i] ) + k1*w[i]  k1-cnt[i]<= k <=k1

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int d=0;d<v;d++){
			head=tail=0;
			k=(V-d)/v;
			for(int j=0;j<=k;j++){
				while(head<tail&&dp[d+j*v]-j*w>=q2[tail-1])
					tail--;
				q[tail]=j;
				q2[tail++]=dp[d+j*v]-j*w;
				while(head<tail&&q[head]<j-c)
					++head;
				dp[d+j*v]=max(dp[d+j*v],q2[head]+j*w);
			}
		}