前言
学习一个新的算法，总是要仔细考虑一些深入的问题，而不要过度追求速度
单调队列是一个主要用来优化 dp 的算法，所以先想出 dp 转移式子，再通过单调队列优化掉一维的复杂度才是正常的打开方式,而不是硬想单调队列怎么做
一般来说，在 dp 式子里有一维"在一个向某一个方向单调移动的区间求最值"，可以尝试单调队列优化
目录
-
A.【例题1】滑动窗口
-
B.【例题2】粉刷木板
-
D.【例题4】燃放烟火
-
E.【例题5】跳房子
-
F.1.最大矩阵
-
G.2.最大指数和
-
H.3.最小间隔
-
I.4.写博客
-
J.5.出题方案
题解
A.【例题1】滑动窗口
题意
分析
单调队列模板题
单调队列，就是一个移动的区间维护最值，内部是一个单调递增或者递减的序列（不严格）
原理：以维护最大值为例。单调队列需要维护队列的左右端点(l,r)，左端点(l)存储区间最大值，队列内是单调递减的，每次更新的时候从队尾插入，同时把队列内(leq)这个新加入的值的元素弹出队列((r--))，因为这些元素不会再对答案有贡献；当左端点(l)不再在区间内时（即随着区间右移，队列左端点离开区间)，就把左端点弹出队列((l++));
这个过程可以用(STL)的(deque)双端队列维护，不过手写也很方便
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f, N = 1e6;
int a[N], n, k;
int p[N], q[N], l = 1, r;
int minn[N], maxn[N], cnt, cnt1;
void work_max() {
for (int i = 1; i <= n; i++) {
while (a[i] >= q[r] && r >= l) {
r--;
}
q[++r] = a[i], p[r] = i;
if (p[l] < i - k + 1)
l++;
if (i >= k)
maxn[++cnt] = q[l];
// printf("[%d,%d]",l,r);
}
}
void work_min() {
l = 1, r = 0;
for (int i = 1; i <= n; i++) {
while (a[i] <= q[r] && r >= l) {
r--;
}
q[++r] = a[i], p[r] = i;
if (p[l] < i - k + 1)
l++;
if (i >= k)
minn[++cnt1] = q[l];
// printf("[%d,%d]",l,r);
}
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
work_max();
work_min();
for (int i = 1; i <= cnt1; i++) printf("%d ", minn[i]);
printf("
");
for (int i = 1; i <= cnt; i++) printf("%d ", maxn[i]);
return 0;
}
B.【例题2】粉刷木板
题意
分析
如果你考虑到 dp 解决这个问题，比较容易想出状态的（因为就题里基本只有这两个参数）:(dp(i,j)&表示前)i(个工匠刷到第)j(个木板（可以有重复）
这里我们规定刷到)j$是从前往后刷
考虑转移，首先对于任何情况，都有：
- 这个工匠不刷任何一个木块：(dp(i,j)=dp(i-1,j))，这个很好理解
- 这个工匠不刷当前的木块：(dp(i,j)=dp(i,j-1))，这个可能有点难理解，因为并不知道为什么单独考虑当前木块。但是换个思路，就是把前一个 dp 先继承过来，防止 dp 值出现下降的情况
然后，对于(j)(leq)(s_i)的情况，设他粉刷的区间是([k+1,j])，则有转移式(dp(i,j)=max)({f(i-1,k)+p_i*(j-k)})((j-l_i)(leq)(k<s_i))如果把(j)提出来，那么式子就只和(k)有关
因此就可以用单调队列省去对(k)的枚举
具体代码实现时，每次先把([max)({0,s_i-l_i})(,s_i-1])区间内的(k)值放入单调队列，在枚举(j)的时候随着区间移动维护单调队列
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 16005,M = 105;
inline ll read()
{
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9')) ch=c,c=getchar();
while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
struct node
{
int l,p,s;
inline bool operator < (const node &oth) const{return s<oth.s;}
}a[M];
int n,m,f[M][N],q[N],l=1,r=0;
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++) a[i].l=read(),a[i].p=read(),a[i].s=read();
sort(a+1,a+m+1);
for(int i=1;i<=m;i++)
{
l=1,r=0;//注意每次重置，初始队列为空
for(int k=max(0,a[i].s-a[i].l);k<=a[i].s-1;k++)
{
while(l<=r&&f[i-1][q[r]]-q[r]*a[i].p<=f[i-1][k]-k*a[i].p) r--;
q[++r]=k;
}
for(int j=1;j<=n;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(j>=a[i].s)
{
while(l<=r&&j-q[l]>a[i].l) l++;
//emm原来写成r--了，实际是弹出队首越界的元素
if(l<=r) f[i][j]=max(f[i][j],f[i-1][q[l]]+(j-q[l])*a[i].p);
//别忘了单调队列的最值在队首...
}
}
}
printf("%d",f[m][n]);
return 0;
}
D.【例题4】燃放烟火
题意
分析
很容易想到设计(dp(i,j))表示前(i)个烟花的时候在第(j)个位置能获得的最大幸福值
转移也比较显然，再枚举一维(k)表示第(i-1)个烟火的时候在什么位置，就有(dp(i,j)=max {dp(i-1,k)} +b_i-abs(a_i-j);)
因为是一个区间单调地向右移动同时维护最大值，所以(k)这一维就可以单调队列优化了
需要注意的是，(j)的循环需要顺序和倒序分别枚举一次，因为要考虑到从(j)的左边和右边走到(j)的两种情况
由于有负值，dp 数组需要稍微特殊处理一下
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 1.5e5+10,M = 305;
inline ll read()
{
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9')) ch=c,c=getchar();
while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
struct node
{
int a,b,t;
inline bool operator < (const node& oth) const {return t<oth.t;}
}f[M];
int dp[M][N];
int n,m,d,q[N];
int main()
{
n=read(),m=read(),d=read();
for(int i=1;i<=m;i++) f[i].a=read(),f[i].b=read(),f[i].t=read();
//sort(f+1,f+m+1); 输入保证t不下降
//memset(dp,-0x3f,sizeof(dp));
//for(int i=1;i<=n;i++) dp[m][i]=-INF;
for(int i=1;i<=m;i++)
{
int l=1,r=0;
for(int j=1;j<=n;j++)
{
while(r>=l&&j-q[l]>(f[i].t-f[i-1].t)*d) l++;
while(r>=l&&dp[i-1][q[r]]<=dp[i-1][j]) r--;
q[++r]=j;
if(r>=l) dp[i][j]=dp[i-1][q[l]]+f[i].b-abs(f[i].a-j);
//printf("dp:%d update
",dp[i-1][q[l]]+f[i].b-abs(f[i].a-j));
}
l=1,r=0;
for(int j=n;j>=1;j--)
{
while(r>=l&&q[l]-j>(f[i].t-f[i-1].t)*d) l++;
while(r>=l&&dp[i-1][q[r]]<=dp[i-1][j]) r--;
q[++r]=j;
if(r>=l) dp[i][j]=max(dp[i][j],dp[i-1][q[l]]+f[i].b-abs(f[i].a-j));
//printf("dp:%d update
",dp[i-1][q[l]]+f[i].b-abs(f[i].a-j));
}
//printf("#%d:(%d,%d)
",i,l,r);
}
int res=-INF;
for(int i=1;i<=n;i++)
res=max(res,dp[m][i]);
printf("%d",res);
return 0;
}
E.【例题5】跳房子
题意
分析
相对比较难的一道题。
F.1.最大矩阵
题意
分析
先说下最简单的思路：可以看作动态维护区间最小值，就是和单调队列模板---滑动窗口模型一样，维护一个单调上升的序列，再枚举区间长度，复杂度(O(n^2)),期望得分(40)分
再说进一步的思路：上一个思路为什么复杂度高，本质在于其枚举区间长度显然是麻烦了。既然对于一个区间，只关心它的区间最小值，那么在找到你一个区间最小值时，肯定是要它的长度越大越好，故不需要枚举区间长度
上述想法反过来进行：对于每个点(i)，用(lst[i])和(nxt[i])分别记录从(i)向左或向右走到的最远的点（的下一个点），使满足(h[t])(geq)(h[i])这样就只需要(O(n))级别的复杂度了
图示如下：
其实只是运用了单调队列的一个思路
代码还有一些细节，写在注释里
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 1e5+10;
int a[N],n,k;
int p[N],q[N],l=1,r;
int cnt;
int lst[N],nxt[N];//分别表示i向左，向右找到的不小于i的最远点
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
/* 中间while更新不应该用t++、t--会超时
lst[1]=1;
for(int i=2;i<=n;i++)
{
int t=i-1;
while(a[i]<=a[t]&&t>0) t--;
t++;
lst[i]=t;
}
nxt[n]=n;
for(int i=1;i<=n-1;i++)
{
int t=i+1;//写的时候要仔细想好边界条件能否都走到
while(a[i]<=a[t]&&t<=n) t++;
t--;
nxt[i]=t;
}
*/
//lst，nxt的定义都往外移动了1位
lst[1]=0;
for(int i=2;i<=n;i++)
{
int t=i-1;
while(a[i]<=a[t]&&t>0) t=lst[t];
lst[i]=t;
}
nxt[n]=n+1;
for(int i=n-1;i>=1;i--)
{
int t=i+1;
while(a[i]<=a[t]&&t<=n) t=nxt[t];
nxt[i]=t;
}
ll ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,1LL*(nxt[i]-lst[i]-1)*a[i]);
printf("%lld",ans);
return 0;
}
G.2.最大指数和
题意
分析
本题看起来非常水（起码我终于可以不看题解写了）
设向右的步数区间是 ([L,R])
但是一开始写的时候遇到一个问题，不会处理(q[l]+L>i)的情况（即当队首位置+最小步数跨过了当前点 (i) 的情况）
这种情况显然不能简单地入队、出队
其实解决方法也很简单，枚举 (i) 的时候从 (L) 开始枚举，每次入队的元素位置从 (i) 改成 (i-L)，就可以避免这个问题
答案要求输出路径，也很简单，记录 (lst[i]) 表示 (i) 从哪一个点转移过来，递归输出即可
最后注意一点：转移 dp 的时候要在更新单调队列之后，不理解这句的就看代码吧
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 2e5+10;
inline ll read()
{
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9')) ch=c,c=getchar();
while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
int n,L,R,l=1,r=0;
int a[N],dp[N],q[N],ed,cnt,lst[N];
void print(int x)
{
if(!lst[x]) {printf("0 ");return;}
print(lst[x]);
printf("%d ",x);
}
int main()
{
n=read(),L=read(),R=read();
for(int i=1;i<=n+1;i++) a[i-1]=read();
for(int i=L;i<=n;i++)
{
while(l<=r&&q[l]+R<i) l++;
while(l<=r&&dp[q[r]]<=dp[i-L]) r--;//弹出单调队列要灵活放置
q[++r]=i-L;
//转移dp要在更新完单调队列的元素之后
lst[i]=q[l];
dp[i]=dp[q[l]]+a[i];
}
int ret=0;
for(int i=n-R;i<=n;i++)
if(ret<dp[i]) ret=dp[i],ed=i;
printf("%d
",ret);
print(ed);
printf("-1
");
return 0;
}
I.4.写博客
有难度的题，请移步本人博客：传送门-写博客
J.5.出题方案
更加有难度的题，请移步本人博客：传送门-出题方案