Eternity

Until The End

单调队列优化Dp

发表于 更新于 分类于 ，
本文字数： 11k 阅读时长 ≈ 10 分钟

“我永远对你保有最诚挚的热情。”

单调队列

单调队列是一种队列内的元素有单调性（递增或递减）的队列。答案（最优解）存在队首。一般用于维护区间最值或者降低 $Dp$ 数组的维度来减少空间及时间的目的。

单调队列的作用 1. 维护区间最值
2. 优化 DP

单调队列在队首和队尾都可以进行出队操作，但只有队尾可以进行入队操作。这样的操作类似于双端队列（$deque$）允许双端弹出。但一般来说，还是不建议使用 $STL$ 库，手写方便且比较节省时间。

总的来说，单调队列的实现有三步：

  1. 将 $head$ 之前所有已在区间之外的答案删掉（ $++head$ ）
  2. 更新答案为 $Queue[head]$
  3. 将尾部的非最优答案排除（ $—tail$ ），并入队最新答案。

栗子

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

题意

求出区间最大值和最小值，因为复杂度限制 $O(n \log n)$ 所以无法暴力。就使用单调队列的优化。

AC Code：

查看代码 
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
using namespace std;
using std::cin;
using std::cout;
int N,K,A[1000001];
int Q[10000001];
int P[10000001],head,tail;
inline void underMax()
{
	head=1;
	tail=0;
	for(int i=1;i<=N;++i)
	{
		while(head<=tail&&Q[tail]<=A[i])
		{
			tail--;
		}
		Q[++tail]=A[i];
		P[tail]=i;
		while(P[head]<=i-K)
		{
			head++;
		}
		if(i>=K)
		{
			printf("%d ",Q[head]);
		}
	}
}
inline void underMin()
{
	head=1;
	tail=0;
	for(int i=1;i<=N;++i)
	{
		while(head<=tail&&Q[tail]>=A[i])
		{
			tail--;
		}
		Q[++tail]=A[i];
		P[tail]=i;
		while(P[head]<=i-K)
		{
			head++;
		}
		if(i>=K)
		{
			printf("%d ",Q[head]);
		}
	}
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%d%d",&N,&K);
	for(int i=1;i<=N;++i)
	{
		scanf("%d",&A[i]);
	}
	underMin();
	printf("\n");
	underMax();
	return 0;
}
/*
8 3
1 3 -1 -3 5 3 6 7
*/

单调队列优化多重背包

巨佬的讲解

Acwing 6 多重背包III

查看代码 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
using namespace std;
using std::cin;
using std::cout;
int n,V;
int v,w,s;
int dp[20001],pre[20001],q[20001];
int main()
{
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;++i)
    {
        memcpy(pre, dp, sizeof(dp));
        int v, w, s;
        cin >>v>>w>>s;
        for (int j=0;j<v;++j)
        {
            int head=0, tail=-1;
            for (int k=j;k<=V;k+=v)
            {
                        if (head<=tail&&k-s*v>q[head]) ++head;
            while(head<=tail&&pre[q[tail]]-(q[tail]-j)/v*w<=pre[k]-(k-j)/v*w) --tail;
            if (head<=tail) dp[k]=max(dp[k],pre[q[head]]+(k-q[head])/v*w);
            q[++tail]=k;
        }
    }
}
printf("%d",dp[V]);
return 0;

提升

P2216 [HAOI2007]理想的正方形

解释

二维的滑动窗口，也就那样做就对了。

AC Code

查看代码 
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1001;
const int INF=0x7f7f7f7f;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),tail=0;
    while(ch<'0'||ch>'9') tail|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(tail) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M,K;
int val[MAXN][MAXN],Row_max[MAXN][MAXN],Row_min[MAXN][MAXN];
int Que[MAXN];
inline void get_min(int a[],int b[],int m)
{
    memset(Que,0,sizeof(Que));
    int head=0,tail=-1;
    for(int i=1;i<=m;++i)
    {
        if(head<=tail&&Que[head]<=i-K) ++head;
        while(head<=tail&&a[Que[tail]]>=a[i]) --tail;
        Que[++tail]=i;
        b[i]=a[Que[head]];
    }
}
inline void get_max(int a[],int b[],int m)
{
    memset(Que,0,sizeof(Que));
    int head=0,tail=-1;
    for(int i=1;i<=m;++i)
    {
        if(head<=tail&&Que[head]<=i-K) ++head;
        while(head<=tail&&a[Que[tail]]<=a[i]) --tail;
        Que[++tail]=i;
        b[i]=a[Que[head]];
    }
}
int main()
{
    // freopen("dp-deque.in","r",stdin);
    // freopen("dp-deque.out","w",stdout);
    read(N,M,K);
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
            read(val[i][j]);
    for(int i=1;i<=N;++i)
    {
        get_min(val[i],Row_min[i],M);
        get_max(val[i],Row_max[i],M);
    }
    int res=INF;
    int a[MAXN],b[MAXN],c[MAXN];
    for(int i=K;i<=M;++i)
    {
        for(int j=1;j<=N;++j) a[j]=Row_min[j][i];
        get_min(a,b,N);
        for(int j=1;j<=N;++j) a[j]=Row_max[j][i];
        get_max(a,c,N);
        for(int j=K;j<=N;++j) res=min(res,c[j]-b[j]);
    }
    printf("%d",res);
    return 0;
}
/*
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
*/

练习

P1440 求m区间内的最小值

P2032 扫描

P1725 琪露诺

单调栈

同样的，表示一个栈 $S$ 中的元素满足单调递增或者单调递减的性质，可以用来维护 RMQ 问题。

栈是一种先进后出、后进先出的数据结构，栈和队列应该是最简单的两种数据结构了，其原理与实现非常简单。单调栈中的元素是严格单调递增或者递减的，也就是说：从栈底到栈顶，元素的值逐渐增大或者减小。虽然单调栈的性质很简单，但是其用处很大，可以用于求解元素的左右大小边界问题。

例题

单调栈模板

对于查询后继的题，具有后效性，对我而言不太好处理；所以我们考虑倒序枚举。将问题转化为查找前继中第一个比该数大的下标，以样例为例：

1
1 4 2 3 5

建立一个单调递减的栈 $S$ ，接下来我们来手动模拟：

1
2
3
4
5
6
7
8
9
10
11
输入 5 
栈为空，则 dp[5]=0 ，将 5 入栈，当前栈为 5 。
输入 3
栈数为 1 ，有 5>3 ，则 dp[4]=5 ，入栈 3 ，当前栈为 5 3
输入 2
栈数为 2 ，有 3>2 ，则 dp[3]=4 ，入栈 2 ，当前栈为 5 3 2
输入 4
栈数为 3 ，有 2<4 ，维护单减性，出栈 2 ，同样出栈 3 ，更新答案为 dp[2]=5 ，入栈 4 ，当前栈为 5 4
输入 1
栈数为 2 ，有 4>1 ，则 dp[1]=2 ，入栈 1 ，当前栈为 5 4 1
结束，答案为 2 5 4 5 0

一些小问题：

  1. 关于栈空的处理，如果是使用 $STL$ 的话，要先判是否为空，否则会 $RE$ 。且对于栈空的情况，有些题目是需要特判的。
  2. 关于取不取等的情况，视题目而定，就这道题而言，因为我们查找的是最近的一个，所以对于有 $a_i=a_j,i<j$ 的话，肯定有 $i$ 答案是更优的，所以在此题，相等情况下是需要出栈的。
AC Code 
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
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=3e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,x[MAXN],Stk[MAXN<<1],Top,dp[MAXN];
int main()
{
    // freopen("stack-monotonous.in","r",stdin);
    // freopen("stack-monotonous.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i) read(x[i]);
    for(int i=N;i>=1;--i)
    {
        while(Top&&x[Stk[Top]]<=x[i]) --Top;
        if(!Top) dp[i]=0;
        else dp[i]=Stk[Top];
        Stk[++Top]=i;
    }
    for(int i=1;i<=N;++i) printf("%d ",dp[i]);
    return 0;
}
/*
5
1 4 2 3 5
*/

巩固

P6510 奶牛排队

考虑枚举右端点 $B$。根据题意，因为左端点 $A$ 一定是最矮的，所以 $A$ 一定是当前序列（从 $1$ 到 $B$）的后缀最小值所在的位置。

因为 $B$ 一定是最高的，所以 $A$ 到 $B$ 之间不能有任何元素比 $B$ 高，因此 $A$ 的右侧一定只有 $B$ 一个位置可以作为当前序列的后缀最大值。换句话说，我们要找到从后向前数第二个后缀最大值的位置 $k$，$A$ 一定在该位置的右侧。并且只要 $A$ 在 $k$ 右侧且 $A$ 是当前序列的后缀最小值，那么 $A$ 就是一个合法的左端点。

考虑用单调栈来维护当前序列的后缀最大最小值，每次新枚举到一个 $B$ 时，先不将新位置入栈，此时的最大值栈顶就是第二个后缀最大值的位置。而维护后缀最小值的单调栈中的下标也是单调的，因此直接在最小值栈上二分即可找到最靠左的对应 $A$ 的位置。更新答案即可。时间复杂度 $\mathcal O(n \log n)$。

AC Code 
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=1e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,x[MAXN],dp[MAXN];
int Stk[2][MAXN<<1],Top[2],ans;
int main()
{
    // freopen("dp-mono.in","r",stdin);
    // freopen("dp-mono.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i)
    {
        read(x[i]);
        while(Top[0]&&x[Stk[0][Top[0]]]>=x[i]) --Top[0];
        while(Top[1]&&x[Stk[1][Top[1]]]< x[i]) --Top[1];
        int k=upper_bound(Stk[0]+1,Stk[0]+1+Top[0],Stk[1][Top[1]])-Stk[0];
        if(k!=(Top[0]+1)) ans=max(ans,i-Stk[0][k]+1);
        Stk[0][++Top[0]]=i;
        Stk[1][++Top[1]]=i;
    }
    printf("%d",ans);
    return 0;
}
/*
5
1
2
3
4
1
*/

P2422 良好的感觉

维护比第 $x$ 个数大的偏左和偏右下标，每一个点贡献的答案就是：

$ans=\max\limits_{1\le i\le n}\{x_i\times(s_{right_i}-s_{left_i-1})\}$

从前往后，从后往前各一次单调栈后统计答案，应该要开 long long ，没试过。

AC Code 
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=1e5+1;
const int INF=0x7f7f7f7f;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,Stk[MAXN<<1],Top;
int Le[MAXN],Ri[MAXN];
ll s[MAXN],x[MAXN],ans;
int main()
{
    // freopen("stack-mono.in","r",stdin);
    // freopen("stack-mono.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i) read(x[i]),s[i]=s[i-1]+x[i];
    x[0]=x[N+1]=-INF;
    Stk[++Top]=0;
    for(int i=1;i<=N;++i)
    {
        while(Top&&x[Stk[Top]]>x[i]) --Top;
        Le[i]=Stk[Top]+1;
        Stk[++Top]=i;
    }
    memset(Stk,0,sizeof(Stk));
    Stk[Top=1]=N+1;
    for(int i=N;i>=1;--i)
    {
        while(Top&&x[Stk[Top]]>x[i]) --Top;
        Ri[i]=Stk[Top]-1;
        Stk[++Top]=i;
    }
    for(int i=1;i<=N;++i) ans=max(ans,x[i]*(s[Ri[i]]-s[Le[i]-1]));
    printf("%lld",ans);
    return 0;
}
/*
6
3 1 6 4 5 2
*/

—

相关文章