空间跳跃 题解

题目分析

小杨在二维空间中有 $n$ 个水平挡板，挡板之间不重叠。他可以在挡板上左右移动，走到端点再向外移动会竖直掉落到下方第一个挡板上。移动和掉落均消耗时间。给定起点挡板 $s$ 和终点挡板 $t$，求从第 $s$ 个挡板的左端点出发，到达第 $t$ 个挡板的任意位置所需的最少时间。若无法到达则输出 $-1$。

核心难点在于：

1. 挡板数量 $n \le 1000$，可以直接 $O(n^2)$ 暴力建图或 DP。
2. 竖直掉落只能从上往下，不能向上，因此存在方向限制。
3. 下落时会落到“下方第一个”挡板，需要快速找到每个端点下方对应的挡板。

解题思路

关键转化

由于只能向下掉落，我们可以将所有挡板按照高度从高到低排序。这样从某个挡板下落时，只需在它下方的挡板中寻找第一个能接住它的即可。

设到达第 $i$ 个挡板的左端点的最小时间为 $dp[i][0]$，右端点的最小时间为 $dp[i][1]$。我们可以在挡板间进行递推。

最终要到达第 $t$ 个挡板的任意位置，因此一旦在掉落过程中直接落在第 $t$ 个挡板上，即可更新全局答案，不需要再走到 $t$ 的端点。

寻找下方第一个挡板

对于挡板 $i$，其左端点横坐标为 $l_i$，右端点为 $r_i$。当从 $i$ 的左端点掉落时，下落轨迹是 $x = l_i$ 的竖直线。它会掉到下方第一个满足 $l_j \le l_i \le r_j$ 且 $h_j<h_i$ 的挡板 $j$ 上。由于已按高度降序排列，我们只需从 $i+1$ 开始向后遍历，找到第一个满足区间覆盖的挡板 $j$ 即可。由于挡板不重叠，这个 $j$ 就是正下方的挡板。

同理，从右端点掉落时寻找 $l_j \le r_i \le r_j$ 的第一个 $j$。

状态转移

假设我们已经知道从起点到挡板 $i$ 左、右端点的最短时间，并找到了其下方挡板 $j$：

• 若从 $i$ 左端点掉落（已花时间 $dp[i][0]$）：

  • 下落高度差 $d_h = h_i - h_j$
  • 落到 $j$ 上的位置是 $x = l_i$
  • 若要走到 $j$ 的左端点 $l_j$，水平花费 $l_i - l_j$，总时间 $dp[i][0] + d_h + (l_i - l_j)$
  • 若要走到 $j$ 的右端点 $r_j$，水平花费 $r_j - l_i$，总时间 $dp[i][0] + d_h + (r_j - l_i)$
  • 若 $j$ 就是终点挡板 $t$，则无需继续走到端点，到达时间就是 $dp[i][0] + d_h$

• 若从 $i$ 右端点掉落（已花时间 $dp[i][1]$）：

  • 落到 $j$ 上的位置是 $x = r_i$
  • 走到 $j$ 左端点：$dp[i][1] + d_h + (r_i - l_j)$
  • 走到 $j$ 右端点：$dp[i][1] + d_h + (r_j - r_i)$
  • 若 $j = t$，到达时间 $dp[i][1] + d_h$

用上述规则更新 $dp[j][0]$、$dp[j][1]$ 以及答案 $ans$ 即可。

起点与不可达情况

• 起点 $s$ 的左端点初始时间 $dp[s][0] = 0$；如果它直接走到右端点，时间 $dp[s][1] = r_s - l_s$。
• 排序后如果起点 $s$ 的高度低于终点 $t$（即排序后 $s$ 的下标大于 $t$），那么无法从高向低到达，直接输出 $-1$。
• 若处理完毕后 $ans$ 仍为初始的极大值，说明无法到达，输出 $-1$。

算法说明

1. 输入 $n, s, t$ 以及每个挡板的 $l_i, r_i, h_i$，为每个挡板记录原始编号 id。
2. 将所有挡板按照 $h$ 降序排序；若 $h$ 相同则按 $l$ 升序。
3. 在排序后的数组中找到 $s$ 和 $t$ 对应的下标。若 $s$ 的下标 $>t$ 的下标，直接输出 $-1$ 并结束。
4. 初始化 $dp[i][0] = dp[i][1] = \infty$（足够大的数），$ans = \infty$。
5. 对于起点 $dp[s][0] = 0$，$dp[s][1] = r_s - l_s$。
6. 从 $s$ 遍历到 $t$（排序后下标）：
   • 对于挡板 $i$，寻找从左端点下落的下方挡板 $j$（$j$ 从 $i+1$ 到 $t$，找到第一个符合 $l_j \le l_i \le r_j$ 的）：
     • $d_h = h_i - h_j$
     • 若 $j = t$，更新 $ans = \min(ans, dp[i][0] + d_h)$
     • 更新 $dp[j][0] = \min(dp[j][0], dp[i][0] + d_h + (l_i - l_j))$
     • 更新 $dp[j][1] = \min(dp[j][1], dp[i][0] + d_h + (r_j - l_i))$
     • 找到后立即 break（不能穿透）。
   • 同理，寻找从右端点下落的下方挡板 $j$（第一个符合 $l_j \le r_i \le r_j$ 的）：
     • $d_h = h_i - h_j$
     • 若 $j = t$，更新 $ans = \min(ans, dp[i][1] + d_h)$
     • 更新 $dp[j][0] = \min(dp[j][0], dp[i][1] + d_h + (r_i - l_j))$
     • 更新 $dp[j][1] = \min(dp[j][1], dp[i][1] + d_h + (r_j - r_i))$
     • break。
7. 若 $ans = \infty$ 则输出 $-1$，否则输出 $ans$。

时间复杂度分析

• 排序：$O(n \log n)$。
• 双循环：对于每个 $i$，寻找下方挡板 $j$ 时最坏需要扫描后面所有元素，复杂度 $O(n^2)$。由于 $n \le 1000$，$n^2 = 10^6$，非常充裕。
• 总复杂度 $O(n^2)$，可以在 $1$ 秒内轻松通过。

参考代码

cpp
复制
1#include<bits/stdc++.h>
2#define int long long
3using namespace std;
4
5struct node{
6    int l, r, h, id; // 左右端点、高度、原始编号
7} a[1010];
8
9int dp[1010][2]; // dp[i][0]: 到达第i个挡板左端点的最短时间
10                  // dp[i][1]: 到达第i个挡板右端点的最短时间
11
12bool cmp(node x, node y) {
13    if (x.h == y.h) return x.l < y.l;
14    return x.h > y.h;        // 按高度从高到低排序
15}
16
17signed main() {
18    ios::sync_with_stdio(false);
19    cin.tie(0); cout.tie(0);
20
21    int n, os, ot;
22    cin >> n >> os >> ot;
23    for (int i = 1; i <= n; i++) {
24        cin >> a[i].l >> a[i].r >> a[i].h;
25        a[i].id = i;
26        dp[i][0] = dp[i][1] = 1e18; // 初始化为极大值
27    }
28
29    sort(a + 1, a + n + 1, cmp);
30
31    int s, t;
32    for (int i = 1; i <= n; i++) {
33        if (a[i].id == os) s = i;
34        if (a[i].id == ot) t = i;
35    }
36
37    // 若起点低于终点（排序后下标更大），则无法到达
38    if (s > t) {
39        cout << "-1\n";
40        return 0;
41    }
42
43    dp[s][0] = 0;                    // 起点左端点
44    dp[s][1] = a[s].r - a[s].l;      // 从起点左端走到右端点
45    int ans = 1e18;
46
47    for (int i = s; i <= t; i++) {
48        // 从左端点下落
49        for (int j = i + 1; j <= t; j++) {
50            if (a[j].l <= a[i].l && a[i].l <= a[j].r && a[i].h > a[j].h) {
51                int val = a[i].h - a[j].h; // 下落时间
52                if (j == t) ans = min(ans, dp[i][0] + val);
53                dp[j][0] = min(dp[j][0], dp[i][0] + (a[i].l - a[j].l) + val);
54                dp[j][1] = min(dp[j][1], dp[i][0] + (a[j].r - a[i].l) + val);
55                break; // 找到正下方第一个挡板，停止
56            }
57        }
58        // 从右端点下落
59        for (int j = i + 1; j <= t; j++) {
60            if (a[j].l <= a[i].r && a[i].r <= a[j].r && a[i].h > a[j].h) {
61                int val = a[i].h - a[j].h;
62                if (j == t) ans = min(ans, dp[i][1] + val);
63                dp[j][0] = min(dp[j][0], dp[i][1] + (a[i].r - a[j].l) + val);
64                dp[j][1] = min(dp[j][1], dp[i][1] + (a[j].r - a[i].r) + val);
65                break;
66            }
67        }
68    }
69
70    if (ans == 1e18) cout << "-1\n";
71    else cout << ans << '\n';
72
73    return 0;
74}

代码说明

• 结构体 node：存储每个挡板的 $l, r, h$ 以及原始 id，用于排序后仍能定位起点 $s$ 和终点 $t$。
• 排序规则：高度降序，同高度按 $l$ 升序（同高度不会发生掉落，排序主要保证下落在后的元素中）。
• dp 数组：定义为全局，最大 $n=1000$，初始值 $10^{18}$ 表示不可达。
• 寻找下方挡板：因为已经排序，$j$ 从 $i+1$ 开始遍历，条件 a[i].h > a[j].h 保证是向下掉落，区间覆盖保证能落到该挡板上。找到第一个即停止。
• 终点更新：当 $j==t$ 时，直接更新答案，无需加上在 $t$ 挡板上的水平移动，因为题目只要求到达挡板 $t$ 任意位置即可。
• 复杂度：两重循环虽然嵌套，但每个 $i$ 内层最坏扫描 $O(n)$，总 $O(n^2)$，完全可行。

总结

本题本质是一个有向无环图上的最短路径问题（DAG 上的 DP）。通过按高度排序，明确了挡板间的依赖关系（只能从上到下），并利用“下方第一个”的条件高效建立转移。读题时要注意到达终点挡板的定义（落在其上即完成），避免加上多余的端点移动代价。