动态规划（算法竞赛、蓝桥杯）--单调队列滑动窗口与连续子序列的最大和

1、B站视频链接：E11【模板】单调队列 滑动窗口最值_哔哩哔哩_bilibili

题目链接：滑动窗口 /【模板】单调队列 - 洛谷

#include <bits/stdc++.h> 
using namespace std;
const int N=1000010;
int a[N],q[N];//q存的是元素的下标 

int main(){
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);

//维护窗口最小值
int h=1,t=0;//清空队列且t在h之前
for(int i=1;i<=n;i++){
while(h<=t&&a[i]<=a[q[t]])t--;//队尾出队（队列不空且新元素更优
q[++t]=i;//队尾入队(存储下标 方便判断队头出队)
if(q[h]<i-k+1)h++;//队头出队滑出了窗口
if(i>=k)printf("%d ",a[q[h]]);//使用最值 
} 
puts("");
//维护窗口最大值
h=1,t=0;
for(int i=1;i<=n;i++){
while(h<=t&&a[i]>=a[q[t]])t--;
q[++t]=i;
if(q[h]<i-k+1)h++;
if(i>=k)printf("%d ",a[q[h]]);
}
return 0;
}

练习题：1、求m区间内的最小值 - 洛谷

2、扫描 - 洛谷    3、 [HAOI2007] 理想的正方形 - 洛谷

2、B站视频链接：E12 单调队列 连续子序列的最大和_哔哩哔哩_bilibili

#include <bits/stdc++.h> 
using namespace std;
const int N=300010;
int n,m;
int s[N],f[N],q[N];

int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&s[i]),s[i]+=s[i-1];//前缀和 
}
int h=1,t=0;//清空队列
for(int i=1;i<=n;i++){//枚举序列 
while(h<=t&&s[i-1]<=s[q[t]])t--;//队尾出队（队尾不空且更优） 
q[++t]=i-1;//队尾入队，存储下标
if(q[h]<i-m)h++;//队头出队滑出窗口
f[i]=s[i]-s[q[h]]; 
}
int res=-2e9;
for(int i=1;i<=n;i++){
res=max(res,f[i]);
} 
printf("%d\n",res);
return 0;
}

 

 

原文地址：https://blog.csdn.net/lmessi10_/article/details/136262978

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！