单调队列优化的DP问题
概述
单调队列就是通过排除求最值时候的冗余,从而是队列具有性质,可以方便求解问题。
DP的两个阶段:
- 朴素DP的基本原理——闫氏DP分析法
- 对朴素DP进行优化
闫氏DP分析法的拓展 :在一个有限的集合中求最值。
单调队列练习
135. 最大子序和
输入一个长度为 n 的整数序列,从中找出一段长度不超过 m 的连续子序列,使得子序列中所有数的和最大。
注意: 子序列的长度至少是 1。
输入格式
第一行输入两个整数 n,m。
第二行输入 n 个数,代表长度为 n 的整数序列。
同一行数之间用空格隔开。
输出格式
输出一个整数,代表该序列的最大子序和。
数据范围
1≤n,m≤300000
输入样例:
6 4
1 -3 5 1 -2 3
输出样例:
7
这道题目是使用暴力的思路想,然后优化。
首先,朴素的思路就是枚举每一个长度不大于m的区间,遍历求最大值。
这里涉及到区间的操作,所以转化为前缀和。
a[x] + ... + a[y] = sum[y] - sum[x - 1]
这时候,我们枚举右端点,sum[y]
已经固定,sum[x]
需要在滑动的区间内取得最小值,所以使用滑动窗口。
#include <bits/stdc++.h>
using namespace std;
#define N 300020
int n, m;
int s[N];// 前缀和
int 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 res = -0x3f3f3f3f;// 由于序列的长度可以为 0
int hh = 0, tt = -1;
q[++tt] = 0;// 由于是前缀和,所以应该 包含0
for(int i = 1; i <= n; i++)
{
while(hh <= tt && q[hh] < i - m) hh ++;
if(hh <= tt)
res = max(s[i] - s[q[hh]], res);
while(hh <= tt && s[q[tt]] >= s[i]) tt --;
q[++tt] = i;
}
printf("%d", res);
return 0;
}
1088. 旅行问题
John 打算驾驶一辆汽车周游一个环形公路。
公路上总共有 n 个车站,每站都有若干升汽油(有的站可能油量为零),每升油可以让汽车行驶一千米。
John 必须从某个车站出发,一直按顺时针(或逆时针)方向走遍所有的车站,并回到起点。
在一开始的时候,汽车内油量为零,John 每到一个车站就把该站所有的油都带上(起点站亦是如此),行驶过程中不能出现没有油的情况。
任务:判断以每个车站为起点能否按条件成功周游一周。
输入格式
第一行是一个整数 n,表示环形公路上的车站数;
接下来 n 行,每行两个整数 pi,di,分别表示表示第 i 号车站的存油量和第 i 号车站到 顺时针方向 下一站的距离。
输出格式
输出共 n 行,如果从第 i 号车站出发,一直按顺时针(或逆时针)方向行驶,能够成功周游一圈,则在第 i 行输出 TAK,否则输出 NIE。
数据范围
3≤n≤1e6
0≤pi≤2×1e9
0≤di≤2×1e9
输入样例:
5
3 1
1 2
5 2
0 1
5 4
输出样例:
TAK
NIE
TAK
NIE
TAK
分析
- 由于要求解顺时针或者是逆时针,这两种情况具有对称性,所以先考虑一种。
- 是一个环,直接求的话不能利用之前已经求解好的状态,所以需要破环成链。
- 可以把
p[i]
和d[i]
做一个差值。满足要求的情况就是从 i 号点到 i + 1 号点的所有前缀全部是大于0的。 - 求解以某一点为结尾的所有不超过n的前缀中的最值问题,就可以使用上一题的思路。
真可谓思路不难,调BUG离谱
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000020
ll p[N], d[N], a[N*2];// a表示前缀
int n;
int q[N*2];
bool ans[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++){
scanf("%lld%lld", p + i, d + i);
}
// 顺时针情况************************************
for(int i = 1; i <= n; i++){
a[i] = p[i] - d[i];
a[i + n] = p[i] - d[i];
}
for(int i = 1; i <= 2 * n; i++){
a[i] = a[i] + a[i - 1];
}
int tt = -1, hh = 0;
for(int i = n * 2; i >= 0; i--)
{
while(hh <= tt && q[hh] > i + n) hh ++;
if(hh <= tt && i < n) {
if(a[i]<=a[q[hh]]) ans[i+1] = true;
// a[i]<=a[q[hh]]表示的是i + 1 到 q[hh]的区间之和大于等于0
}
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
}
// 逆时针情况************************************
d[0] = d[n];
for(int i = 1; i <= n; i++){
a[i + n] = a[i] = p[i] - d[i - 1];
}
a[0] = 0;
for(int i = 1; i <= 2 * n; i++){
a[i] = a[i] + a[i - 1];
}
tt = -1, hh = 0;
q[++tt] = 0;
for(int i = 1; i <= n * 2; i++)
{
while(hh <= tt && q[hh] < i - n) hh ++;
if(hh <= tt && i > n) {
if(a[q[hh]] <= a[i]) ans[i - n] = true;
// a[i]<=a[q[hh]]表示的是q[hh]+1到i的区间之和大于等于0
}
while(hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
}
for(int i = 1; i <= n; i++){
if(ans[i]){
puts("TAK");
}else{
puts("NIE");
}
}
return 0;
}
二维单调队列问题
1091. 理想的正方形
有一个 a×b 的整数组成的矩阵,现请你从中找出一个 n×n的正方形区域,使得该区域所有数中的最大值和最小值的差最小。
输入格式
第一行为三个整数,分别表示 a,b,n 的值;
第二行至第 a+1 行每行为 b 个非负整数,表示矩阵中相应位置上的数。
输出格式
输出仅一个整数,为 a×b 矩阵中所有“n×n 正方形区域中的最大整数和最小整数的差值”的最小值。
数据范围
2≤a,b≤1000,
n≤a,n≤b,n≤100,
矩阵中的所有数都不超过 1e9。
输入样例:
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
输出样例:
1
这一道题目算是一个典型的二维的滑动窗口问题。
如果直接滑动,那么会比较复杂。所以我们先按照行来,存储row_max[i][j]
为以[i][j]
结尾的,每行的最值。
然后对于row_max[i][j]
再纵着来一下就可以了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1020;
int w[N][N];
int row_max[N][N];
int row_min[N][N];
int n, m, K;
int q[N];
void getmax(int *a, int *b, int tot)
{
int tt = -1, hh = 0;
for(int i = 1; i <= tot; i++){
while(hh <= tt && q[hh] <= i - K) hh++;
while(hh <= tt && a[q[tt]] <= a[i]) tt--;// BUG1: a[q[tt]] <= a[i]写反了
q[++tt] = i;
if(hh <= tt) b[i] = a[q[hh]];
}
}
void getmin(int *a, int *b, int tot)
{
int tt = -1, hh = 0;
for(int i = 1; i <= tot; i++){
while(hh <= tt && q[hh] <= i - K) hh++;
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
if(hh <= tt) b[i] = a[q[hh]];
}
}
int main()
{
scanf("%d%d%d", &n, &m, &K);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
scanf("%d", &w[i][j]);
}
for(int i = 1; i <= n; i++){
getmax(w[i], row_max[i], m);
getmin(w[i], row_min[i], m);
// BUG3:getmin(w[i], row_max[i], m);
}
static int a[N], b[N], c[N];
int res = 0x7f7f7f7f;
for(int i = K; i <= m; i++)
{
for(int j = 1; j <= n; j++) a[j] = row_max[j][i];// BUG 2:要从1开始(虽然K之前不参与更新res,但是参与求最值)
getmax(a, b, n);
for(int j = 1; j <= n; j++) a[j] = row_min[j][i];
getmin(a, c, n);
for(int i = K; i <= n; i++) res = min(res, b[i] - c[i]);
}
printf("%d\n", res);
return 0;
}
使用单调队列来优化DP
1089. 烽火传递
烽火台是重要的军事防御设施,一般建在交通要道或险要处。
一旦有军情发生,则白天用浓烟,晚上有火光传递军情。
在某两个城市之间有 n 座烽火台,每个烽火台发出信号都有一定的代价。
为了使情报准确传递,在连续 m 个烽火台中至少要有一个发出信号。
现在输入 n,m 和每个烽火台的代价,请计算在两城市之间准确传递情报所需花费的总代价最少为多少。
输入格式
第一行是两个整数 n,m,具体含义见题目描述;
第二行 n 个整数表示每个烽火台的代价 ai。
输出格式
输出仅一个整数,表示最小代价。
数据范围
1≤m≤n≤2e5
0≤ai≤1000
输入样例:
5 3
1 2 5 6 2
输出样例:
4
这一道题目可能会想到状态机,但是使用状态机的话就必须有m个状态,并不切合实际。
设状态:f[i]
表示从第一个到第 i 个,并且第 i 个被点燃的情况下的最小花费。
我们把n+1
的代价视为0,点燃n + 1视为DP结束。
对于当前的,选择dp[i - m], dp[i - m + 1] ..... d[i -1]
中的最小的,这满足滑动窗口
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int n, m;
int dp[N];
int q[N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", a+i);
int hh = 0, tt = -1;
q[++tt] = 0;
for(int i = 1; i <= n + 1; i ++){
while(hh <= tt && q[hh] < i - m) hh ++;
if(hh <= tt) dp[i]= dp[q[hh]] + a[i];
while(hh <= tt && dp[q[tt]] >= dp[i]) tt --;
q[++tt] = i;// 注意:队列里面存放的一直都是下标
}
printf("%d\n", dp[n + 1]);
//for(int i = 1; i <= n+1; i++) cout << dp[i] << " ";
return 0;
}
1090. 绿色通道
高二数学《绿色通道》总共有 n 道题目要抄,编号 1,2,…,n,抄第 i 题要花 ai 分钟。
小 Y 决定只用不超过 t 分钟抄这个,因此必然有空着的题。
每道题要么不写,要么抄完,不能写一半。
下标连续的一些空题称为一个空题段,它的长度就是所包含的题目数。
这样应付自然会引起马老师的愤怒,最长的空题段越长,马老师越生气。
现在,小 Y 想知道他在这 t 分钟内写哪些题,才能够尽量减轻马老师的怒火。
由于小 Y 很聪明,你只要告诉他最长的空题段至少有多长就可以了,不需输出方案。
输入格式
第一行为两个整数 n,t。
第二行为 n个整数,依次为 a1,a2,…,an
输出格式
输出一个整数,表示最长的空题段至少有多长。
数据范围
0<n≤5e4
0<ai≤3000
0<t≤1e8
输入样例:
17 11
6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5
输出样例:
3
题解
这一道题目在具体做决定的时候,会发现并不知道最终答案,导致过程中无法把握舍与得。
这时候我们可以想到使用二分答案。
容易得知,显然具有单调性。
二分之后,就是相当于判断相邻两个最远的距离是mid,求出抄完的时间满不满足。
(大致思路和上一道题目类似)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 20;
int a[N];
int T, n;
int f[N], q[N];
bool ck(int mid)
{
int hh = 0, tt = -1;
q[++tt] = 0;
for(int i = 1; i <= n + 1; i++){
while(hh <= tt && q[hh] < i - mid - 1) hh ++;
if(hh <= tt) f[i] = f[q[hh]] + a[i];
while(hh <= tt && f[q[tt]]>= f[i]) tt --;
q[++tt] = i;
}
//cout << mid << " " << f[n + 1] << "\n";
if(f[n + 1] <= T) return true;
else return false;
}
int main()
{
scanf("%d%d", &n, &T);
for(int i = 1; i <= n; i++) scanf("%d", a + i);
int l = 0, r = n;
while(l < r){
int mid = (l + r) >> 1;
if(ck(mid)) r = mid;
else l = mid + 1;
}
printf("%d", l);
return 0;
}
1087. 修剪草坪
在一年前赢得了小镇的最佳草坪比赛后,FJ 变得很懒,再也没有修剪过草坪。
现在,新一轮的最佳草坪比赛又开始了,FJ 希望能够再次夺冠。
然而,FJ 的草坪非常脏乱,因此,FJ 只能够让他的奶牛来完成这项工作。
FJ 有 N 只排成一排的奶牛,编号为 1 到 N。
每只奶牛的效率是不同的,奶牛 i 的效率为 Ei。
编号相邻的奶牛们很熟悉,如果 FJ 安排超过 K 只编号连续的奶牛,那么这些奶牛就会罢工去开派对。
因此,现在 FJ 需要你的帮助,找到最合理的安排方案并计算 FJ 可以得到的最大效率。
注意,方案需满足不能包含超过 K 只编号连续的奶牛。
输入格式
第一行:空格隔开的两个整数 N 和 K;
第二到 N+1行:第 i+1 行有一个整数 Ei。
输出格式
共一行,包含一个数值,表示 FJ 可以得到的最大的效率值。
数据范围
1≤N≤1e5
0≤Ei≤1e9
输入样例:
5 2
1
2
3
4
5
输出样例:
12
样例解释
FJ 有 5 只奶牛,效率分别为 1、2、3、4、5。
FJ 希望选取的奶牛效率总和最大,但是他不能选取超过 2 只连续的奶牛。
因此可以选择第三只以外的其他奶牛,总的效率为 1 + 2 + 4 + 5 = 12。
题解一
其实从上面两道题目中可以看出来:
对于区间中连续的m个中,必须选择一个
这种情况,可以使用单调队列进行优化。
所以,在这里可以反过来思考,这样就转化为了上面的思路。
f[i]
表示不选择第 i 个数字,在前 i 个数字中不选择的数字加起来的最小值。
在任意一个连续的区间内,需要满足在 K+1 的范围内至少有一个不选择。
最后使用总的和减去上述求出的结果就行。
题解二-y总思路
状态表示:f[i]
表示从前 i 个奶牛中选择,并且满足没有连续选择超过 K 头奶牛的所有情况。
属性:最大值。
转移:
- 不选择第 i 头奶牛,那么
f[i] = f[i - 1]
- 选择第 i 头奶牛
这时候应该注意不能让连续的大于K
对于第二种情况:
枚举x\((1\le x\le K)\),表示选择了包括 i 在内的从后往前数的连续 x 个奶牛,第 \(i - x\)头奶牛不选的所有情况中的最大值。
由于涉及到区间问题,转化为前缀和。
有状态转移公式:f[i] = s[i] - s[i - x] + f[i - x - 1]
\((1\le x\le K)\)
为了方便表示,令\(g(x) = f[x - 1] - s[x]\)
边界情况:
\(g(0)\):这种情况表示的是从 1 到 i 全部选择的情况。应该为0.
\(g(1)\):f[0]
为0,表示不选择任何奶牛的最大值。
#include <bits/stdc++.h>
using namespace std;
int n, K;
const int N = 1e5 + 20;
typedef long long ll;
ll s[N];
ll f[N];
ll q[N];
inline ll g(ll x){
if(!x) return 0;
return f[x - 1] - s[x];
}
int main()
{
scanf("%d%d", &n, &K);
for(int i = 1; i <= n; i++){
scanf("%lld", s + i);
s[i] += s[i - 1];
}
int hh = 0, tt = -1;
q[++tt] = 0;
for(int i = 1; i <= n; i++)
{
while(hh <= tt && q[hh] < i - K) hh ++;
if(hh <= tt) f[i] = max(f[i - 1], s[i] + g(q[hh]));
// BUG 记录:只顾着写单调队列优化了,忘了还有不选择这种情况
while(hh <= tt && g(q[tt]) <= g(i)) tt--;
q[++tt] = i;
}
printf("%lld", f[n]);
return 0;
}
标签:输出,队列,tt,样例,整数,int,DP,奶牛,单调
From: https://www.cnblogs.com/xjsc01/p/17029229.html