文章目录
  1. 1. 单调队列
    1. 1.1. TYVJ1305
    2. 1.2. BZOJ 3831
    3. 1.3. 洛谷 P3800 Power收集
    4. 1.4. POJ 2373 Dividing the Path

引言:单调队列及DP优化


单调队列

单调队列维护队列一定满足某个优先条件。

单调队列与优先队列的区别:单调队列的长度取决于输入数据的合法性,而优先队列的长度始终与输入数据的数量等同。而他们的单调性都是单调递减或单调递增。

因此单调队列的性能一般比优先队列高。

单调(队列/栈)是一种有着DP思想的数据结构,它维护一个满足特殊单调性的序列,这种单调性保证每个元素在全局上都有成为最优答案的可能,而不满足这种单调性的元素在之后的统计中一定不会对答案产生任何贡献,需要及时删除。https://blog.csdn.net/fantasy_world/article/details/79592284

一般使用双端队列实现(好写),开个数组模拟即可。或者使用STL的deque。

在单调队列中的元素一般是下标值。

TYVJ1305

题解:https://blog.csdn.net/fantasy_world/article/details/79592284

OJ:http://www.joyoi.cn/problem/tyvj-1305

优先队列(耗时410ms,内存5.5MiB):

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
#include<bits/stdc++.h>

using namespace std;
#define MAXN 300010
#define INF 0x3f3f3f3f
int n,m;
int a[MAXN];
int s[MAXN];
class st{
public:
int v,i;
bool operator < (const st &a) const{
if(this->v==a.v){
return this->i>a.i;
}
return this->v<a.v;
}
bool operator > (const st &a) const{
return !(*this<a);
}
};

int main(){
priority_queue<st,vector<st>,greater<st> > q;
while(cin>>n>>m){
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
int maxn=-INF;
q.push(st{0,0});
for(int i=1;i<=n;i++){
while(!q.empty() && i-q.top().i>m){
q.pop();
}
maxn=max(maxn,s[i]-q.top().v);
maxn=max(maxn,s[i]-q.top().v);
q.push(st{s[i],i});
}
cout<<maxn<<endl;
}
return 0;
}

单调队列(耗时290ms,内存4.9MiB):

  1. 为什么使得l=r=1?

    为了让r–后落入有效index

  2. 为什么使得l=r,且判断条件是l<=r?

    相当于一开始push了一个0

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
#include<bits/stdc++.h>

using namespace std;
#define MAXN 300010
#define INF 0x3f3f3f3f
int n,m;
int a[MAXN];
int s[MAXN];
int q[MAXN];
int l=1,r=1;

int main(){
while(cin>>n>>m){
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
int maxn=-INF;
for(int i=1;i<=n;i++){
while(l<=r && i-q[l]>m){
l++;
}
maxn=max(maxn,s[i]-s[q[l]]);
while(l<=r && s[q[r]]>=s[i]){
r--;
}
q[++r]=i;
}
cout<<maxn<<endl;
}
return 0;
}

单调队列,使用deque(耗时300ms,内存5.0MiB):

可以看到代码简单易懂了很多。

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
#include<bits/stdc++.h>

using namespace std;
#define MAXN 300010
#define INF 0x3f3f3f3f
int n,m;
int a[MAXN];
int s[MAXN];
deque<int> dq;

int main(){
while(cin>>n>>m){
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
int maxn=-INF;
dq.push_back(0);
for(int i=1;i<=n;i++){
while(!dq.empty() && i-dq.front()>m){
dq.pop_front();
}
maxn=max(maxn,s[i]-s[dq.front()]);
while(!dq.empty() && s[dq.back()]>=s[i]){
dq.pop_back();
}
dq.push_back(i);
}
cout<<maxn<<endl;
}
return 0;
}

BZOJ 3831

OJ:https://www.luogu.org/fe/problem/P3572

有一排n棵树,第i棵树的高度是Di。

MHY要从第一棵树到第n棵树去找他的妹子玩。

如果MHY在第i棵树,那么他可以跳到第i+1,i+2,…,i+k棵树。

如果MHY跳到一棵不矮于当前树的树,那么他的劳累值会+1,否则不会。

为了有体力和妹子玩,MHY要最小化劳累值。

方程是

dp[i]=min(dp[j]+(h[j]<=h[i]))dp[i]=\min(dp[j]+(h[j]<=h[i]))

可以看出很明显的滑动窗口,窗口大小是K。可以用单调队列进行DP优化。

如果不优化,复杂度是O(nk)的,优化后复杂度是O(n)线性的(假设维护单调队列的复杂度忽略不计)。

很显然,dp[j]和dp[i]最多相差1,把dp放在单调队列里先按大小排,小的排前面;再按树高排,树高的排前面;再维持滑动窗口。

这样排有什么好处呢?当dp在队列中只有一个最小值时,很显然选它就可以了(如果选次小值,即使跳时不消耗体力也相当于选最小值跳时消耗体力)。

当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
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000010

int h[MAXN];
int dp[MAXN];
int N,Q;
int k;
deque <int> dq;

int main(){
while(~scanf("%d",&N)){
for(int i=1;i<=N;i++){
scanf("%d",h+i);
}
scanf("%d",&Q);
for(int i=0;i<Q;i++){
memset(dp,0,sizeof(dp));
dq.clear();
scanf("%d",&k);
for(int i=1;i<=N;i++){
while(!dq.empty() && i-dq.front()>k){
dq.pop_front();
}
if(!dq.empty()){
dp[i]=dp[dq.front()];
if(h[dq.front()]<=h[i]){
dp[i]++;
}
}
while(!dq.empty() && (dp[dq.back()]>dp[i] || (dp[dq.back()]==dp[i] && h[dq.back()]<h[i]))){
dq.pop_back();
}
dq.push_back(i);
}
printf("%d\n",dp[N]);
}
}
return 0;
}

洛谷 P3800 Power收集

https://www.luogu.org/problemnew/show/P3800

题目描述

可以把游戏界面理解成一个N行M列的棋盘,有K个格子上有P点,其价值为val(i,j)

初始灵梦可以选择在第一行的任意一个格子出发,每秒她必须下移一格。

灵梦具有一个左右移动的速度T,可以使她每秒向左或右移动至多T格,也可以不移动,并且不能折返。移动可视为瞬间完成,不经过路途上的点,只能获得目标格子的P点。

求最终她能获得的POWER值最大是多少?

显然需要维护一个滑动窗口,窗口大小2k。

需要注意的是在移动到下一行时,单调队列需要清空,并且在最开始要push一些初始元素。

单调队列维护一个-k~k的区间:

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
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

int n,m,k,t;
int mat[4010][4010];
int q[4010];
int l=1,r=0;


void in(int center,int i,int row){
if(i<0 || i>=m){
return ;
}
while(l<=r && mat[row][q[r]]<=mat[row][i]){
--r;
}
q[++r]=i;
}

int main(){
scanf("%d%d%d%d",&n,&m,&t,&k);
memset(mat,0,sizeof(mat));
for(int i=0;i<t;i++){
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
mat[x-1][y-1]=v;
}
for(int i=1;i<n;i++){
l=1,r=0;
for(int j=0;j<=k && j<m;j++){
in(0,j,i-1);
}
for(int j=0;j<m;j++){
while(l<=r && abs(q[l]-j)>k){
++l;
}
if(l<=r)mat[i][j]+=mat[i-1][q[l]];
//printf("|(%d,%d):%d->(%d,%d):%d|",i-1,q[l],mat[i-1][q[l]],i,j,mat[i][j]);
if(j+k+1<m)
in(j+1,j+k+1,i-1);
}
}
int maxn=-INF;
for(int i=0;i<m;i++){
maxn=max(maxn,mat[n-1][i]);
}
printf("%d\n",maxn);
return 0;
}

deque版本:

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
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

int n,m,k,t;
int mat[4010][4010];

int main(){
scanf("%d%d%d%d",&n,&m,&t,&k);
memset(mat,0,sizeof(mat));
for(int i=0;i<t;i++){
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
mat[x-1][y-1]=v;
}
deque<int> dq;
for(int i=1;i<n;i++){
for(int j=0;j<=k && j<m;j++){
while(!dq.empty() && mat[i-1][dq.back()]<=mat[i-1][j]){
dq.pop_back();
}
dq.push_back(j);
}
for(int j=0;j<m;j++){
while(!dq.empty() && abs(dq.front()-j)>k){
dq.pop_front();
}
if(!dq.empty())mat[i][j]+=mat[i-1][dq.front()];
if(j+k+1<m){
while(!dq.empty() && mat[i-1][dq.back()]<=mat[i-1][j+k+1]){
dq.pop_back();
}
dq.push_back(j+k+1);
}
}
}
int maxn=-INF;
for(int i=0;i<m;i++){
maxn=max(maxn,mat[n-1][i]);
}
printf("%d\n",maxn);
return 0;
}

POJ 2373 Dividing the Path

https://vjudge.net/problem/POJ-2373

https://vjudge.net/problem/HYSBZ-1986

这道题的坑点比较多,很多细节问题,帮我复习了很多知识。

比方说:

  1. 在最开始审题时,可能会考虑到:奶牛的活动范围可以交叉,意味着三种关系:1,包含关系。2,交叉关系。3,分离关系。当出现前两个关系时,合并奶牛,以使得简化问题。但实际上不需要考虑这些情况,因为奶牛活动范围只决定了dp转移范围。
  2. 奶牛所在的活动范围,两个端点是可以去掉的,因为端点可以被两个花洒同时覆盖,而中间的点不可以。不要担心活动范围只有1和2的奶牛因此丢失,其实没有任何影响。
  3. 2a必定大于最大的奶牛的去端点的活动范围(实际上没有任何用)。
  4. 在这道题deque不需要判空,但做了总比不做强。
  5. 在初始化dp数组时,最好将除了可转移点都初始化为非法值INF,用m[i]==0来判断是否为转移落点(见下代码)。防止发生意外(经验,感谢喵老板),在此题中意外表现为当一次转移都不发生时,即L过小时,应当输出1而不是0。
  6. 在区间覆盖时,如果考虑左右端点,应当为m[left]++,m[right+1]--,这里去端点则m[left+1]++,m[right]--。不要写成m[left]=1,m[right]=-1,某两区间左右端点重合时会出事的。
  7. 记得i+2而不是i++,花洒直径是个偶数,L也是偶数(L是偶数算是题目故意给的提示以降低难度吧)。

喵老板说:DP必须要思路特别清晰的时候才能一次做对。

这次我们都attempt了7、8次,在理清思路之后花了一个小时码代码,坤坤也思考并码了一个小时。

单调队列无脑维护一个0~2b的区间:

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
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<deque>
#include<cstring>
using namespace std;
#define maxlen 1000010
#define INF 0x3f3f3f3f
int n,l,a,b;
int m[maxlen];
int dp[maxlen];

int main(){
while(~scanf("%d%d%d%d",&n,&l,&a,&b)){
a*=2;
b*=2;
memset(m,0,sizeof(m));
for(int i=0;i<n;i++){
int s,e;
scanf("%d%d",&s,&e);
m[s+1]++;
m[e]--;
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=l;i++){
m[i]+=m[i-1];
dp[i]=INF;
}
deque<int> dq;
dq.clear();
dq.push_back(0);
for(int i=2;i<=l;i+=2){
while(i-dq.front()>b){
dq.pop_front();
}
deque<int>::iterator iter;
for(iter=dq.begin();iter!=dq.end() && i-*iter<a;iter++);
if(iter==dq.end()){
dp[i]=INF;
continue;
}
if(!m[i])dp[i]=dp[*iter]+1;
//printf("|%d->%d,%d=>%d|",*iter,i,dp[*iter],dp[i]);
while(dp[i]<dp[dq.back()]){
dq.pop_back();
}
dq.push_back(i);//为什么后push这个i,因为i不在转移范围之内
}
printf("%d\n",dp[l]>=INF?-1:dp[l]);
}
return 0;
}

单调队列维护一个2a~2b的区间:

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
#include<cstdio>
#include<deque>
#include<cstring>
using namespace std;
#define maxlen 1000010
#define INF 0x3f3f3f3f
int n,l,a,b;
int m[maxlen];
int dp[maxlen];

int main(){
while(~scanf("%d%d%d%d",&n,&l,&a,&b)){
a*=2;
b*=2;
memset(m,0,sizeof(m));
for(int i=0;i<n;i++){
int s,e;
scanf("%d%d",&s,&e);
m[s+1]++;
m[e]--;
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=l;i++){
m[i]+=m[i-1];
dp[i] = INF;//经验问题,非可转移点应全设为非法值
}
deque<int> dq;
dq.clear();
for(int i=a;i<=l;i+=2){
while(!dq.empty() && dp[i-a]<dp[dq.back()]){//为什么先push这个i-a,是因为i-a也在转移范围之内
//printf("==pop_back: %d==",dq.back());
dq.pop_back();
}
dq.push_back(i-a);
while(!dq.empty() && i-dq.front()>b){
//printf("==pop_front: %d==",dq.front());
dq.pop_front();
}
if(!m[i])dp[i] = dp[dq.front()] + 1;
//printf("|%d->%d,%d=>%d|",dq.front(),i,dp[dq.front()],dp[i]);
}
printf("%d\n",dp[l]>=INF?-1:dp[l]);
}
return 0;
}
文章目录
  1. 1. 单调队列
    1. 1.1. TYVJ1305
    2. 1.2. BZOJ 3831
    3. 1.3. 洛谷 P3800 Power收集
    4. 1.4. POJ 2373 Dividing the Path