- 1JDK的安装配置与Eclipse的安装（win10）_jdk20适用于哪个版本的eclipse
- 2自动驾驶全栈学习路线汇总！十三个主流方向都在这里了~
- 3接口测试-面试题_接口测试面试题
- 4服务器数据恢复—Raid5阵列热备盘上线过程中断导致阵列崩溃的数据恢复案例
- 5NISP，CISP考试费用与含金量_nisp申请cisp花多少钱
- 6论文阅读_csdn阅读论文
- 7SaaS 多租户【字段隔离】_请求的租户标识未传递,请进行排查
- 8Leetcode 378. 有序矩阵中第 K 小的元素_378 有序矩阵 对角线
- 9opencv模糊图像变清晰_去卷积：怎么把模糊的图像变清晰？
- 10【深度学习基础】CSPNet——PyTorch实现CSPDenseNet和CSPResNeXt_cspnet结构
DP + 单调队列--如何利用滑动窗口优化DP_单调队列优化dp的细节
赞
踩
本文介绍单调队列模板以及其在DP中的具体应用
滑动窗口 /【模板】单调队列
题目描述
有一个长为 n n n 的序列 a a a，以及一个大小为 k k k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如：
The array is [ 1 , 3 , − 1 , − 3 , 5 , 3 , 6 , 7 ] [1,3,-1,-3,5,3,6,7] [1,3,−1,−3,5,3,6,7], and k = 3 k = 3 k=3。
输入格式
输入一共有两行，第一行有两个正整数
n
,
k
n,k
n,k。
第二行
n
n
n 个整数，表示序列
a
a
a
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
样例 #1
样例输入 #1
8 3
1 3 -1 -3 5 3 6 7
- 1
- 2
样例输出 #1
-1 -3 -3 -3 3 3
3 3 5 5 6 7
- 1
- 2
提示
【数据范围】
对于
50
%
50\%
50% 的数据，
1
≤
n
≤
1
0
5
1 \le n \le 10^5
1≤n≤105；
对于
100
%
100\%
100% 的数据，
1
≤
k
≤
n
≤
1
0
6
1\le k \le n \le 10^6
1≤k≤n≤106，
a
i
∈
[
−
2
31
,
2
31
)
a_i \in [-2^{31},2^{31})
ai∈[−231,231)。
#include <bits/stdc++.h> using namespace std; int q[1000005]; int a[1000005]; int n,k; int main() { cin >> n >> k; //个数与窗口长度 for(int i = 1; i <= n; i ++) cin >> a[i]; int hh = 1, tt = 0; //队列首尾下标定义，要注意 for(int i = 1; i <= n; i ++) { // 接下来即将入队的元素下标为i while(hh <= tt && i >= q[hh] + k) hh ++; //队头的生命周期已完结，把头弹出 while(hh <= tt && a[i] <= a[q[tt]]) tt --; //新元素比队尾更小，那么它入队之后新元素永无天日，弹出算了 q[++ tt] = i; //新元素的下标入队 if(i < k) continue; //前期窗口还没填满不可以输出哦 cout << a[q[hh]]; //每次都输出队头，队头永远是最小值 if(i != n) cout << ' '; else cout << endl; } hh = 1, tt = 0; for(int i = 1; i <= n; i ++) { while(hh <= tt && i >= q[hh] + k) hh ++; //队头元素的生命已到期 while(hh <= tt && a[i] >= a[q[tt]]) tt --; //即将进入一个比队尾更大的，队尾那个已无用 q[++ tt] = i; //正式入队，队里存的是下标哦 if(i < k) continue; cout << a[q[hh]]; if(i != n) cout << ' '; } return 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
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
在一个限定的窗口内完成目标都可以考虑用单调队列，不过下面这题只是利用了窗口的限定属性，没有体现单调性
[蓝桥杯 2018 省 B] 日志统计
题目描述
小明维护着一个程序员论坛。现在他收集了一份“点赞”日志，日志共有
N
N
N 行。其中每一行的格式是 ts id，表示在
t
s
ts
ts 时刻编号
i
d
id
id 的帖子收到一个“赞”。
现在小明想统计有哪些帖子曾经是“热帖”。如果一个帖子曾在任意一个长度为 D D D 的时间段内收到不少于 K K K 个赞，小明就认为这个帖子曾是“热帖”。
具体来说，如果存在某个时刻 T T T 满足该帖在 [ T , T + D ) [T,T+D) [T,T+D) 这段时间内（注意是左闭右开区间）收到不少于 K K K 个赞，该帖就曾是“热帖”。
给定日志，请你帮助小明统计出所有曾是“热帖”的帖子编号。
输入格式
第一行包含三个整数 N N N、 D D D 和 K K K。
以下 N N N 行每行一条日志，包含两个整数 t s ts ts 和 i d id id。
输出格式
按从小到大的顺序输出热帖 i d id id。每个 i d id id 一行。
样例 #1
样例输入 #1
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
样例输出 #1
1
3
- 1
- 2
提示
对于 50 % 50\% 50% 的数据， 1 ≤ K ≤ N ≤ 1000 1 \le K \le N \le 1000 1≤K≤N≤1000。
对于 100 % 100\% 100% 的数据， 1 ≤ K ≤ N ≤ 1 0 5 1 \le K \le N \le 10^5 1≤K≤N≤105， 0 ≤ i d , t s ≤ 1 0 5 0 \le id, ts \le 10^5 0≤id,ts≤105。
时限 1 秒, 256M。蓝桥杯 2018 年第九届省赛
#include <bits/stdc++.h> using namespace std; int N, D, K; vector <int> id[100005]; int q[100005]; int main() { cin >> N >> D >> K; for(int i = 1; i <= N; i ++) { int t, a; cin >> t >> a; id[a].push_back(t); } for(int i = 0; i <= 100000; i ++) { if(id[i].size() < K) continue; sort(id[i].begin(), id[i].end()); //时间从小到大 int hh = 1, tt = 0; q[0] = 0, q[1] = 0; //清空队列 //队列里直接存时间 for(int j = 0; j < id[i].size(); j ++) { while(hh <= tt && q[hh] + D <= id[i][j]) hh ++; //即将放入的时间与队头冲突 while(hh <= tt && id[i][j] >= q[tt] + D) tt --; //即将放入的时间与队尾冲突 q[++ tt] = id[i][j]; if(tt - hh + 1 >= K) { cout << i << endl; break; } } } return 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
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
接下来才是本文重点，具体的单调队列优化DP
[NOIP2017 普及组] 跳房子
题目背景
NOIP2017 普及组 T4
题目描述
跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下：
在地面上确定一个起点，然后在起点右侧画 n n n 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个 格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：
玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。
现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 d d d。小 R 希望改进他的机器人，如果他花 g g g 个金币改进他的机器人，那么他的机器人灵活性就能增加 g g g，但是需要注意的是，每 次弹跳的距离至少为 1 1 1。具体而言，当 g < d g<d g<d 时，他的机器人每次可以选择向右弹跳的距离为 d − g , d − g + 1 , d − g + 2 , … , d + g − 1 , d + g d-g,d-g+1,d-g+2,\ldots,d+g-1,d+g d−g,d−g+1,d−g+2,…,d+g−1,d+g；否则当 g ≥ d g \geq d g≥d 时，他的机器人每次可以选择向右弹跳的距离为 1 , 2 , 3 , … , d + g − 1 , d + g 1,2,3,\ldots,d+g-1,d+g 1,2,3,…,d+g−1,d+g。
现在小 R 希望获得至少 k k k 分，请问他至少要花多少金币来改造他的机器人。
输入格式
第一行三个正整数 n , d , k n,d,k n,d,k ，分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数。相邻两个数 之间用一个空格隔开。
接下来 n n n 行，每行两个整数 x i , s i x_i,s_i xi,si ，分别表示起点到第 i i i 个格子的距离以及第 i i i 个格子的分数。两个数之间用一个空格隔开。保证 x i x_i xi 按递增顺序输入。
输出格式
共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 k k k 分，输出 − 1 -1 −1。
样例 #1
样例输入 #1
7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
样例输出 #1
2
- 1
样例 #2
样例输入 #2
7 4 20
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
样例输出 #2
-1
- 1
提示
输入输出样例 1 说明
花费 2 2 2 个金币改进后，小 R 的机器人依次选择的向右弹跳的距离分别为 $ 2, 3, 5, 3, 4,3$，先后到达的位置分别为 2 , 5 , 10 , 13 , 17 , 20 2, 5, 10, 13, 17, 20 2,5,10,13,17,20，对应$ 1, 2, 3, 5, 6, 7$ 这 6 6 6 个格子。这些格子中的数字之和 $ 15$ 即为小 R 获得的分数。
输入输出样例 2 说明
由于样例中 7 7 7 个格子组合的最大可能数字之和只有 18 18 18，所以无论如何都无法获得 20 20 20 分。
数据规模与约定
本题共 10 组测试数据，每组数据等分。
对于全部的数据满足 1 ≤ n ≤ 5 × 1 0 5 1 \le n \le 5\times10^5 1≤n≤5×105， 1 ≤ d ≤ 2 × 1 0 3 1 \le d \le2\times10^3 1≤d≤2×103， 1 ≤ x i , k ≤ 1 0 9 1 \le x_i, k \le 10^9 1≤xi,k≤109， ∣ s i ∣ < 1 0 5 |s_i| < 10^5 ∣si∣<105。
对于第 1 , 2 1, 2 1,2 组测试数据，保证 n ≤ 10 n\le 10 n≤10。
对于第 3 , 4 , 5 3, 4, 5 3,4,5 组测试数据，保证 n ≤ 500 n \le 500 n≤500。
对于第 6 , 7 , 8 6, 7, 8 6,7,8 组测试数据，保证 d = 1 d = 1 d=1。
先写了一遍暴力DP，着重解释一下f[0]为什么初始化成1，因为在状态转移过程中，祖先状态如果分别是0和一个负数，那么取max会拿到0的那个状态，但是0状态也有可能是之前压根没有走到过的状态，所以f[0]初始化成1，这样能够走到的所有状态都不可能为0，转移之前只要判断一下该状态是否为0就能判断该状态是否是有效状态了
更新一下：f [ 0 ] = 1这种标记方式有bug，当有效状态为-1 时，由于标记的原因加上1反而变成了无效状态，所以最好还是把f数组初始化成负无穷然后f [ 0 ] = 0；
#include <bits/stdc++.h> using namespace std; int n, k, d; int x[500005], s[500005]; int f[500005]; bool check(int g) { memset(f, 0, sizeof f); f[0] = 1; if(g < d) { for(int i = 1; i <= n; i ++) { for(int j = 0; j < i; j ++) { if(x[i] - x[j] <= d + g && x[i] - x[j] >= d - g && x[i] - x[j] >= 1 && f[j]) f[i] = max(f[i], f[j] + s[i]); if(f[i] > k) return true; } } } else { for(int i = 1; i <= n; i ++) { for(int j = 0; j < i; j ++) { if(x[i] - x[j] <= d + g && x[i] - x[j] >= 1 && f[j]) f[i] = max(f[i], f[j] + s[i]); if(f[i] > k) return true; } } } return false; } int main() { cin >> n >> d >> k; //格子数，固定距离，目标分数 for(int i = 1; i <= n; i ++) cin >> x[i] >> s[i]; int l = 0, r = x[n]; while(l <= r) { int mid = l + r >> 1; if(check(mid)) r = mid - 1; else l = mid + 1; } if(l == x[n] + 1) cout << -1; else cout << l; return 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
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
由于check中的双重循环,T得很自然。。接下来介绍单调队列优化
m是最小步长，M是最大步长
用 j 来表示状态 i 要从哪个状态转移过来 每个i 对应一次状态转移，所以是线性时间复杂度，在保证 j 不会靠 i 太近的前提下，先判断状态 j 是否是有效状态（有效状态一定不为0）然后在将 j 入队之前，队列中比 f [ j ] 小的都不可能成为 f [ i ]的前身了，因为它们如果可以的话，那f [ j ] 也完全可以，如果不排出的话它们甚至可能会在后来的 i 中超过距离最大值，但你完全不用担心j 距离不足最小值，因为连当前的i 都大于最小值了，后来的距离只会更远，所以多余状态直接排出，排完将 j 入队，之后重复这个过程直到 j 与 i 的距离到最小值
接下来，需要判断队头与 i 的距离是否超过最大值， 超过的话赶紧排出，因为现在都超了，i 再变大只会更超
排完之后，队头就是一个最大的有效状态了，用它来更新f [ i ] 即可
更新一下：f [ 0 ] = 1这种标记方式有bug，当有效状态为-1 时，由于标记的原因加上1反而变成了无效状态，所以最好还是把f数组初始化成负无穷然后f [ 0 ] = 0；
#include <bits/stdc++.h> using namespace std; int n, k, d; int x[500005], s[500005]; int f[500005],q[500005]; bool check(int g) { memset(f, 0, sizeof f); memset(q, 0, sizeof q); f[0] = 1; //先加上最后再减掉，这样路径上不会存在0，状态在遇到0和负数的时候能够选择最大负数，值为0是走不到的格子 int m = max(d - g, 1), M = d + g; int hh = 1, tt = 0; int j = 0; for(int i = 1; i <= n; i ++) { while(j < i && x[i] - x[j] >= m) { if(f[j]) { while(f[q[tt]] <= f[j] && hh <= tt) tt --; q[++ tt] = j; } j ++; } while(x[i] - x[q[hh]] > M && hh <= tt) hh ++; if(hh <= tt) f[i] = f[q[hh]] + s[i]; if(f[i] > k) return true; } return false; } int main() { cin >> n >> d >> k; //格子数，固定距离，目标分数 for(int i = 1; i <= n; i ++) cin >> x[i] >> s[i]; int l = 0, r = x[n]; while(l <= r) { int mid = l + r >> 1; if(check(mid)) r = mid - 1; else l = mid + 1; } if(l == x[n] + 1) cout << -1; else cout << l; return 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
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
这里再加一道单调队列优化的DP题，这次没有用f[ 0] = 1，标记路径，因为有个HACK数据把我代码卡掉一个点，所以才发现这个问题，以后还是老实初始化成负无穷吧
琪露诺
题目描述
在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。
某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。
小河可以看作一列格子依次编号为 0 0 0 到 N N N，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子 i i i 时，她只移动到区间 [ i + L , i + R ] [i+L,i+R] [i+L,i+R] 中的任意一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。
每一个格子都有一个冰冻指数 A i A_i Ai，编号为 0 0 0 的格子冰冻指数为 0 0 0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数 A i A_i Ai。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。
但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。
开始时，琪露诺在编号 0 0 0 的格子上，只要她下一步的位置编号大于 N N N 就算到达对岸。
输入格式
第一行三个正整数 N , L , R N, L, R N,L,R。
第二行共 N + 1 N+1 N+1 个整数，第 i i i 个数表示编号为 i − 1 i-1 i−1 的格子的冰冻指数 A i − 1 A_{i-1} Ai−1。
输出格式
一个整数，表示最大冰冻指数。
样例 #1
样例输入 #1
5 2 3
0 12 3 11 7 -2
- 1
- 2
样例输出 #1
11
- 1
提示
对于 60 % 60\% 60% 的数据， N ≤ 1 0 4 N \le 10^4 N≤104。
对于 100 % 100\% 100% 的数据， N ≤ 2 × 1 0 5 N \le 2\times 10^5 N≤2×105，$-10^3 \le A_i\le 10^3 $，$1 \le L \le R \le N $。数据保证最终答案不超过 2 31 − 1 2^{31}-1 231−1。
#include <bits/stdc++.h> using namespace std; const int N = 200005; int n, l, r; int a[2 * N], q[2 * N], f[2 * N]; int main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> l >> r; for(int i = 0; i <= n; i ++) { cin >> a[i]; } for(int i = 1; i <= 2 * n; i ++) f[i] = -99999999; //memset正无穷：0x3f, 0x7f 负无穷：0xc0 //f[0] = 1;这种标记路径的方式是错的 //如果f[i] = -1，标记加上1就会变成无效状态 int hh = 1, tt = 0, j = 0; for(int i = 1; i <= 2 * n; i ++) { while(i - l >= j) //先卡最小距离 { if(f[j] > -99999999) { while(hh <= tt && f[j] >= f[q[tt]]) tt --; q[++ tt] = j; } j ++; } while(hh <= tt && q[hh] + r < i) hh ++; //剩下的，就是可用的最大状态 if(hh <= tt) f[i] = f[q[hh]] + a[i]; } int ans = - 100000000; for(int i = n; i <= 2 * n; i ++) { if(f[i] > -99999999) ans = max(ans, f[i]); } cout << ans; return 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
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
