CF1407D - Description
有 \(n\) 栋楼，每栋楼有高度 \(h_i\)，对于第 \(i\) 栋楼和第 \(j\) 栋楼，如果 \((i,j)\) 满足以下三个条件中的任意一个，我们认为可以从第 \(i\) 栋楼跳到第 \(j\) 栋楼：
- \(i+1=j\)
- \(\max(h_{i+1},h_{i+2},\cdots ,h_{j-1})<\min(h_i,h_j)\)
- \(\min(h_{i+1},h_{i+2},\cdots ,h_{j-1})>\max (h_i,h_j)\)
问你从第 \(1\) 栋楼开始，最少跳几次能跳到第 \(n\) 栋楼？
\(2\le n\le 3\times 10^5\)。
CF1407D - Solution
我们设计一个 \(f_i\) 表示从 \(1\) 走到 \(i\) 的最少步数。
对于限制 \(1\)，容易得到 \(f_i=f_{i-1}+1\)。
限制 \(2\) 就是说对于所有 \(i<k<j\)，\(i\) 都是 \(k\) 左侧第一栋比 \(h_k\) 高的楼，\(j\) 都是 \(k\) 右侧第一栋比 \(h_k\) 高的楼。这种左边/右边第一个大于/小于的题很容易想到单调栈求出 \(lft\) 和 \(rgt\)。
我们从 \(i\) 往前找，遍历每一个 \(h_j<h_i\) 的点，如果 \(j\) 满足 \(\max\{ h_{j+1},\cdots ,h_{i-1} \}<h_j\)，就可以从 \(j\) 跳到 \(i\)。我们发现这个条件就等于在讲对于 \(i\) 更新单调栈时会弹出 \(j\)，于是维护单调栈的时候顺手计算就行。一个细节是如果 \(h_j=h_i\)，是无法从 \(j\) 跳到 \(i\) 的，注意特判。
#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n,h[300005];
stack<int>q,qq;
long long dp[300005];
signed main(){cin>>n;for(int i=1;i<=n;i++){cin>>h[i];dp[i]=INT_MAX;}dp[1]=0;q.push(1);qq.push(1);for(int i=2;i<=n;i++){int lst=INT_MAX;while(!q.empty()&&h[q.top()]>=h[i]){dp[i]=min(dp[i],dp[q.top()]+1);lst=h[q.top()];q.pop();}if(!q.empty()&&lst!=h[i]){dp[i]=min(dp[i],dp[q.top()]+1);}q.push(i);lst=INT_MAX;while(!qq.empty()&&h[qq.top()]<=h[i]){dp[i]=min(dp[i],dp[qq.top()]+1);lst=h[qq.top()];qq.pop();}if(!qq.empty()&&lst!=h[i]){dp[i]=min(dp[i],dp[qq.top()]+1);}qq.push(i);}cout<<dp[n]<<endl;return 0;
}