【Codeforces Round #669 (Div. 2) D】Discrete Centrifugal Jumps
Codeforces div round
2023-09-14 09:03:41 时间
题目链接
翻译
你在位置 \(1\),然后想要到位置 \(n\),每个位置都有一个高度 \(h[i]\), 你可以从位置 \(i\) 跳到位置 \(j\), 当且仅当以下情况之一满足:
- \(i + 1 = j\)
- \(min(h[i],h[j]) > max(h[i+1..j-1])\) 即 \(i\) 到 \(j\) 这一段里的每个位置的高度都低于 \(h[i]\) 和 \(h[j]\)
- \(max(h[i],h[j]) < min(h[i+1..j-1])\) 即 \(i\) 到 \(j\) 这一段里的每个位置的高度都高于 \(h[i]\) 和 \(h[j]\)
问你从位置 \(1\) 跳到位置 \(n\) 最少需要跳多少次。
题解
刚开始在做这道题的时候,老想着对于每一个 \(i\) 会不会对应特别多的 \(j\)。
但其实我们可以这样想,假设我们现在要考察 \(x\) 能跳到哪个位置 \(y\),我们不妨先假设 \(x+1..y-1\) 这一段是全都大于 \(h[x]\) 和 \(h[y]\) 的,即我们翻译中的第三种情况。
那么我们分两类情况讨论:
- 第一类, \(h_x<=h_y\), 这种情况,因为 \(h_{x+1..y}\) 都是大于 \(h_y\) 的,那么这里的 \(h_x\) 实际上就是 \(y\) 左边最靠右的小于 \(h_y\) 的位置,显然这样的 \(x\) 是只有一个的,因为是 左边最靠右的。
- 第二类, \(h_x>h_y\), 这种情况,我们类似地,可以得到 \(h_y\) 是 \(x\) 右边最靠左的小于 \(h_x\) 的位置, 对于 \(x\) 来说,这样的 \(y\) 也是唯一的。
\(x+1..y-1\) 这一段全都小于 \(h[x]\) 和 \(h[y]\) 的情况则类似, 也同样的是得到 \(x\) 和 \(y\) 对应的唯一的一个能跳到的位置。
经过上面的分析的话,不难发现每个位置 \(x\) 能够跳到的位置 \(y\) 其实最多只有 \(4\) 个。
注意到 左边最靠右的小于/大于 某个数的情况,和 右边最靠左的小于/大于 某个数的情况是一个经典的能用单调栈解决的问题(或者你也可以称呼它为只在一端操作的单调队列)。
这道题的话,每个位置需要从左往右维护上升下降栈,然后从右往左也同样要维护上升下降栈。
因此,对于每个位置 \(x\) 分别处理出来它能跳到的位置 \(y\),然后进行 \(dp\) 的转移即可 (\(dp_i\) 为到达位置 \(i\) 所需要的最少步骤数)。
最后输出 \(dp[n]\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5;
int n;
int h[N + 10],incStack[N + 10],topInc,decStack[N + 10],topDec;
vector<int> g[N + 10];
int dp[N + 10];
int main(){
#ifdef LOCAL_DEFINE
freopen("E://9.AlgorithmCompetition//Visitor.txt","r",stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
cin >> n;
for (int i = 1;i <= n; i++){
cin >> h[i];
if (i < n){
g[i].push_back(i);
}
}
topInc = 0,topDec = 0;
for (int i = 1;i <= n; i++){
while (topInc > 0 && h[incStack[topInc]] > h[i]) {
topInc--;
}
//h[incStack[topInc]] <= h[i]
if (topInc > 0){
g[incStack[topInc]].push_back(i);
}
incStack[++topInc] = i;
while (topDec > 0 && h[decStack[topDec]] < h[i]){
topDec--;
}
//h[decStack[topDec]] >= h[i]
if (topDec > 0){
g[decStack[topDec]].push_back(i);
}
decStack[++topDec] = i;
}
topInc = 0,topDec = 0;
for (int i = n;i >= 1; i--){
while (topInc > 0 && h[i] < h[incStack[topInc]]){
topInc--;
}
if (topInc > 0){
g[i].push_back(incStack[topInc]);
}
incStack[++topInc] = i;
while (topDec > 0 && h[i] > h[decStack[topDec]]){
topDec--;
}
if (topDec > 0){
g[i].push_back(decStack[topDec]);
}
decStack[++topDec] = i;
}
for (int i = 1;i <= n; i++){
dp[i] = n + 10;
}
dp[1] = 0;
for (int i = 1;i <= n; i++){
int len = g[i].size();
for (int j = 0;j < len; j++){
int y = g[i][j];
dp[y] = min(dp[y],dp[i] + 1);
}
}
cout << dp[n] << endl;
return 0;
}
相关文章
- 【Codeforces Round #695 (Div. 2) A】Wizard of Orz
- 【Codeforces Round #694 (Div. 1) D】Strange Housing
- 【Codeforces Round #694 (Div. 2) C】Strange Birthday Party
- 【Educational Codeforces Round 81 (Rated for Div. 2) C】Obtain The String
- 【Codeforces Round #507 (Div. 2, based on Olympiad of Metropolises) B】Shashlik Cooking
- 【Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) A】 Doggo Recoloring
- 【Codeforces Round #499 (Div. 2) E】Border
- 【Codeforces Round #476 (Div. 2) [Thanks, Telegram!] A】Paper Airplanes
- 【Codeforces Round #476 (Div. 2) [Thanks, Telegram!] C】Greedy Arkady
- 【Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined) B】 Conan and Agasa play a Card Game
- 【Codeforces Round #446 (Div. 2) A】Greed
- 【Codeforces Round #301 (Div. 2) B】 School Marks
- 【Codeforces Round #433 (Div. 1) C】Boredom(二维线段树)
- 【Codeforces Round #433 (Div. 2) C】Planning
- 【Codeforces Round #430 (Div. 2) B】Gleb And Pizza
- 【Codeforces Round #428 (Div. 2) B】Game of the Rows
- 【Codeforces Round #426 (Div. 2) B】The Festive Evening
- 【Codeforces Round #422 (Div. 2) C】Hacker, pack your bags!(hash写法)
- Codeforces Round #256 (Div. 2) B. Suffix Structures(模拟)
- Codeforces Round #253 (Div. 1) B. Andrey and Problem
- Codeforces Round #216 (Div. 2) E. Valera and Queries (BIT)
- Codeforces Round #459 (Div. 2)
- Educational Codeforces Round 34 (Rated for Div. 2)
- Codeforces Round #447 (Div. 2)
- Codeforces Round #441 (Div. 2, by Moscow Team Olympiad)
- 树状数组 Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2) C. Fountains
- Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2) 一夜回到小学生