G8006 [GESP202406 八级] 空间跳跃 题解

知识点：动态规划、几何建模、拓扑顺序。

解题思路

为每块挡板的左右端点记录最短到达时间，按高度从高到低处理。可先沿板移动到另一端，再从端点垂直落到正下方最高的挡板，并更新其两端；到目标挡板时直接记到达时间。

为什么正确

移动只能沿板或下落，高度严格递减使板间图无环；端点是唯一离板位置，记录两端足以描述所有后续选择。

易错点

起点是s板左端；落到目标板即完成，不必再走到端点；只能落在下方第一块挡板，不能跳过它。

复杂度

时间O(n²)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,s,t;
    cin>>n>>s>>t;
    --s;
    --t;
    vector<int>l(n),r(n),h(n);
    for(int i=0;i<n;i++)cin>>l[i]>>r[i]>>h[i];
    vector<array<long long,2>>dp(n);
    for(auto &x:dp)x.fill(1LL<<60);
    dp[s][0]=0;
    vector<int>order(n);
    iota(order.begin(),order.end(),0);
    sort(order.begin(),order.end(),[&](int u,int v){return h[u]>h[v];});
    long long ans=s==t?0:1LL<<60;
    for(int u:order) {
        long long a=dp[u][0],b=dp[u][1];
        dp[u][0]=min(a,b+r[u]-l[u]);
        dp[u][1]=min(b,a+r[u]-l[u]);
        for(int side=0;side<2;side++) {
            int x=side?r[u]:l[u],v=-1;
            for(int j=0;j<n;j++)if(h[j]<h[u]&&l[j]<=x&&x<=r[j]&&(v<0||h[j]>h[v]))v=j;
            if(v<0)continue;
            long long cost=dp[u][side]+h[u]-h[v];
            if(v==t)ans=min(ans,cost);
            dp[v][0]=min(dp[v][0],cost+x-l[v]);
            dp[v][1]=min(dp[v][1],cost+r[v]-x);
        }
    }
    cout<<(ans==(1LL<<60)?-1:ans);
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。