本文共 2961 字，大约阅读时间需要 9 分钟。

upd: 2021.4.28 添加滑动窗口模板供参考。

目录

简介
滑动窗口模板
例题

简介

单调队列是如何优化DP的呢？其实就是推柿子（找到状态转移方程），然后借助柿子里面连续的特征，利用单调队列将查询最值的代价变低，进而达到优化的目的。

滑动窗口模板

模板题传送门：

代码中的单调队列是双端队列实现的，这里说一下用手写双端队列的基本操作：
检验队列非空：tt>=hh
弹出队头：hh++
弹出队尾：tt--
插入队尾：v[++tt]=插入值

代码：

#include<bits/stdc++.h>using namespace std;const int N=1e6+5;int q[N], tt=-1, hh=0;int w[N];int main(){    int n, k; cin>>n>>k;    for(int i=1; i<=n; i++) cin>>w[i];        for(int i=1; i<=n; i++){        while(tt>=hh && q[hh]+k<=i) hh++;         while(tt>=hh && w[i]<=w[q[tt]]) tt--;        q[++tt]=i;        if(i>=k) cout<<w[q[hh]]<<' ';    }    cout<<endl;    tt=-1, hh=0;    for(int i=1; i<=n; i++){        while(tt>=hh && q[hh]+k<=i) hh++;        while(tt>=hh && w[i]>=w[q[tt]]) tt--;        q[++tt]=i;        if(i>=k) cout<<w[q[hh]]<<' ';    }    cout<<endl;    return 0;}

例题

例1：
传送门：

分析：\(f[i]\) 表示前 \(i\) 个烽火台的最小代价，其中第 \(i\) 个是点燃的。
那么我们便得到状态转移方程： \(f[i]=\min(f[i-1],...,f[i-m+1])+w[i]\)

如果直接利用上面的方程进行DP，那么复杂度是 \(O(N^2)\) ，自然是超时的。

注意到随着 \(i\) 的连续变化，\(\min\) 所包含的区间也是连续变化的，即写下 \(i,i+1\) 的情况，\(\min\) 所包括的区间也偏移一个单位：

于是我们可以利用单调队列的思想来维护这个 \(\min\) 。

代码：

#include<bits/stdc++.h>using namespace std;const int N=2e5+5;int f[N], w[N];int n, m;int q[N];int main(){	cin>>n>>m;	for(int i=1;i<=n;i++) cin>>w[i];		int tt=0, hh=0;		for(int i=1;i<=n;i++){		while(tt>=hh && i-q[hh]>m) hh++;		// upd f[]		f[i]=f[q[hh]]+w[i];		while(tt>=hh && f[i]<=f[q[tt]]) tt--;		q[++tt]=i;	}		int ans=0x3f3f3f3f;	for(int i=n-m+1; i<=n; i++) ans=min(ans, f[i]);	cout<<ans<<endl;		return 0;}

例2：
传送门：
分析：\(f[i]\) 表示在前 \(i\) 个奶牛中合法选取方案的最大贡献。
分情况讨论：

• 第 \(i\) 个奶牛没有选取，那么 \(f[i]=f[i-1]\)
• 否则，选取了包括 \(i\) 以及前面的奶牛总共连续 \(j\) 头。可以得到转移方程： \(f[i]=\max(f[i-j-1]-s[i-j])+s[i]\) ，其中 \(j \in [1,k]\) （ \(k\) 为题目允许连续的最大数量）

那么我们拿单调队列维护一下 \(v[i]=f[i-1]-s[i]\) ，这样就能做到 \(O(1)\) 查询最值了。

代码：

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e5+5;int w[N];ll f[N], v[N], s[N];int q[N];int main(){	int n, k; cin>>n>>k;	for(int i=1;i<=n;i++) cin>>w[i], s[i]=s[i-1]+w[i];		f[0]=0;	int tt=0, hh=0;	for(int i=1;i<=n;i++){		while(tt>=hh && q[hh]+k<i) hh++;		f[i]=max(v[q[hh]]+s[i], f[i-1]);				v[i]=f[i-1]-s[i];		while(tt>=hh && v[i]>=v[q[tt]]) tt--;		q[++tt]=i;	}	cout<<f[n]<<endl;		return 0;}

例3：
传送门：
分析：二分一下两个题目之间的长度 \(len\) ，然后对于这样的 \(len\) ，看看能不能做到选取最小代价的合法（即距离不超过 \(len\)）物品即可。（除了二分外与例1完全类似）

代码：

#include<bits/stdc++.h>using namespace std;const int N=50005;int n, t;int w[N];int f[N];int q[N];bool check(int len){	int tt=0, hh=0;	f[0]=0;		int sze=len+1; // the size of the window	for(int i=1;i<=n;i++){		while(tt>=hh && q[hh]+sze<i) hh++;		f[i]=f[q[hh]]+w[i];		while(tt>=hh && f[i]<=f[q[tt]]) tt--;		q[++tt]=i;	}		int res=0x3f3f3f3f;	for(int i=n-sze+1; i<=n; i++) res=min(res, f[i]);		return res<=t;}int main(){	cin>>n>>t;	for(int i=1;i<=n;i++) cin>>w[i];		int l=1, r=N;	while(l<r){		int mid=l+r>>1;		if(check(mid)) r=mid;		else l=mid+1;	}	cout<<l<<endl;		return 0;}