洛谷P10726[GESP202406八级]空间跳跃C++完整题解

一、题目链接 P10726 [GESP202406 八级] 空间跳跃 - 洛谷 二、解题思路

我们要对输入的挡板进行排序，按高度从高到低（从小到大）。

排序之后s和t都要更新。

struct Baffle { int l, r; int h; int id; } b[1005]; void Sort() { sort(b + 1, b + 1 + n, cmp); for (int i = 1; i <= n; i++) { if (b[i].id == os) s = i; if (b[i].id == ot) t = i; } }

对于每个挡板，我们都计算出跳到它左端的最小用时和跳到它右端的最小用时，因为要想继续跳到另一个挡板上，必须先到达出发挡板的左端或者右端再往下跳。

如图，要想从A到B，只有从左侧下和从右侧下两种方式。

那么，我们把到板块i左端点的最短时间记为dp[i][0]；

同理，我们把到板块i右端点的最短时间记为dp[i][1]；

根据上方规则，我们可以推断出：

// 从右跳下 dp[j][0] = min(dp[j][0], dp[i][1] + b[i].h - b[j].h + b[i].r - b[j].l); dp[j][1] = min(dp[j][1], dp[i][1] + b[i].h - b[j].h + b[j].r - b[i].r); // 道理同上 for (int i = s; i <= t; i++) { // 从左跳下 for (int j = i + 1; j <= t; j++) { if (b[i].l >= b[j].l && b[i].l <= b[j].r && b[i].h > b[j].h) { if (j == t) ans = min(ans, dp[i][0] + b[i].h - b[j].h); dp[j][0] = min(dp[j][0], dp[i][0] + b[i].h - b[j].h + b[i].l - b[j].l); dp[j][1] = min(dp[j][1], dp[i][0] + b[i].h - b[j].h + b[j].r - b[i].l); break; } } // 从右跳下 for (int j = i + 1; j <= t; j++) { if (b[i].r >= b[j].l && b[i].r <= b[j].r && b[i].h > b[j].h) { if (j == t) ans = min(ans, dp[i][1] + b[i].h - b[j].h); dp[j][0] = min(dp[j][0], dp[i][1] + b[i].h - b[j].h + b[i].r - b[j].l); dp[j][1] = min(dp[j][1], dp[i][1] + b[i].h - b[j].h + b[j].r - b[i].r); break; } } } 三、完整代码 #include <iostream> #include <cstring> #include <algorithm> using namespace std; struct Baffle { int l, r; int h; int id; } b[1005]; int n, s, t,os,ot; bool cmp(const Baffle& a, const Baffle& b) { if(a.h != b.h) return a.h > b.h; return a.l < b.l; } void Sort() { sort(b + 1, b + 1 + n, cmp); for (int i = 1; i <= n; i++) { if (b[i].id == os) s = i; if (b[i].id == ot) t = i; } } int main() { cin >> n >> os >> ot; for (int i = 1; i <= n; i++) cin >> b[i].l >> b[i].r >> b[i].h, b[i].id = i; Sort(); int dp[1005][2], ans = 0x3f3f3f3f; memset(dp, 0x3f, sizeof (dp)); dp[s][0] = 0, dp[s][1] = b[s].r - b[s].l; for (int i = s; i <= t; i++) { // 从左跳下 for (int j = i + 1; j <= t; j++) { if (b[i].l >= b[j].l && b[i].l <= b[j].r && b[i].h > b[j].h) { if (j == t) ans = min(ans, dp[i][0] + b[i].h - b[j].h); dp[j][0] = min(dp[j][0], dp[i][0] + b[i].h - b[j].h + b[i].l - b[j].l); dp[j][1] = min(dp[j][1], dp[i][0] + b[i].h - b[j].h + b[j].r - b[i].l); break; } } // 从右跳下 for (int j = i + 1; j <= t; j++) { if (b[i].r >= b[j].l && b[i].r <= b[j].r && b[i].h > b[j].h) { if (j == t) ans = min(ans, dp[i][1] + b[i].h - b[j].h); dp[j][0] = min(dp[j][0], dp[i][1] + b[i].h - b[j].h + b[i].r - b[j].l); dp[j][1] = min(dp[j][1], dp[i][1] + b[i].h - b[j].h + b[j].r - b[i].r); break; } } } cout << (ans == 0x3f3f3f3f ? -1 : ans) << endl; return 0; }