题目概述

有 $n$ 个建筑物，高度 $h_i$ 。要从 $1$ 跳到 $n$ ，求最少跳跃步数。$i\to j$ 的跳跃要求：

• $i+1=j$
• $\max(h_{i + 1}, \ldots, h_{j - 1}) < \min(h_i, h_j)$
• $\max(h_i, h_j) < \min(h_{i + 1}, \ldots, h_{j - 1})$

解题报告

下面用 $\max(h_{i + 1}, \ldots, h_{j - 1}) < \min(h_i, h_j)$ 举例，另一种情况同理。

先用单调栈处理出 $L_i$ 表示 $i$ 向左能到达的最远处，$R_i$ 表示 $i$ 向右能到达的最远处（途中都比 $h_i$ 低）。

定义 $f_i$ 表示跳到 $i$ 的答案，除了 $i-1$ 之外，还有两种情况能转移到 $i$ ：

1. $L_{i}-1$ 号建筑（显然 $L_i-1$ 不比 $i$ 低，也比它们之间的高）
2. $[L_i,i-1]$ 区间中，$R_j=i-1$ 的建筑 $j$（能到 $i-1$ 说明比 $[j+1,i-1]$ 的高）

我们对每个 $i$ 建一棵线段树，对于第二种情况，只需要询问 $i-1$ 线段树中 $[L_i,i-1]$ 区间的最小值。

用动态开点线段树即可。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=300000,maxt=12600000;

int n,H[maxn+5],Lmin[maxn+5],Rmin[maxn+5],Lmax[maxn+5],Rmax[maxn+5];
int top,stk[maxn+5],f[maxn+5],ro[2][maxn+5];
int si,ls[maxt+5],rs[maxt+5],MIN[maxt+5];

void Make(){
    for (int i=n;i;i--){
        while (top && H[stk[top]]<=H[i]) Lmin[stk[top]]=i+1,top--;
        stk[++top]=i;
    }
    while (top) Lmin[stk[top--]]=1;
    for (int i=1;i<=n;i++){
        while (top && H[stk[top]]<=H[i]) Rmin[stk[top]]=i-1,top--;
        stk[++top]=i;
    }
    while (top) Rmin[stk[top--]]=n;
    for (int i=n;i;i--){
        while (top && H[stk[top]]>=H[i]) Lmax[stk[top]]=i+1,top--;
        stk[++top]=i;
    }
    while (top) Lmax[stk[top--]]=1;
    for (int i=1;i<=n;i++){
        while (top && H[stk[top]]>=H[i]) Rmax[stk[top]]=i-1,top--;
        stk[++top]=i;
    }
    while (top) Rmax[stk[top--]]=n;
}
void Insert(int &p,int pos,int F,int l=1,int r=n){
    if (!p) p=++si;if (l==r) {MIN[p]=F;return;} int mid=l+(r-l>>1);
    if (pos<=mid) Insert(ls[p],pos,F,l,mid); else Insert(rs[p],pos,F,mid+1,r);
    if (!ls[p] || !rs[p]) MIN[p]=MIN[ls[p]+rs[p]]; else MIN[p]=min(MIN[ls[p]],MIN[rs[p]]);
}
int Ask(int p,int L,int R,int l=1,int r=n){
    if (!p) return 1e9;if (L==l && r==R) return MIN[p]; int mid=l+(r-l>>1);
    if (R<=mid) return Ask(ls[p],L,R,l,mid); else if (L>mid) return Ask(rs[p],L,R,mid+1,r);
    else return min(Ask(ls[p],L,mid,l,mid),Ask(rs[p],mid+1,R,mid+1,r));
}
int main(){
    freopen("D.in","r",stdin);freopen("D.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&H[i]);Make();
    Insert(ro[0][Rmin[1]],1,0);Insert(ro[1][Rmax[1]],1,0);
    for (int i=2;i<=n;i++){
        f[i]=f[i-1]+1;
        f[i]=min(f[i],Ask(ro[0][i-1],Lmin[i],i-1)+1);
        f[i]=min(f[i],Ask(ro[1][i-1],Lmax[i],i-1)+1);
        if (Lmin[i]>1 && H[Lmin[i]-1]>=H[i]) f[i]=min(f[i],f[Lmin[i]-1]+1);
        if (Lmax[i]>1 && H[Lmax[i]-1]<=H[i]) f[i]=min(f[i],f[Lmax[i]-1]+1);
        Insert(ro[0][Rmin[i]],i,f[i]);Insert(ro[1][Rmax[i]],i,f[i]);
    }
    printf("%d\n",f[n]);return 0;
}