欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：P10726 [GESP202406 八级] 空间跳跃 - 洛谷 (luogu.com.cn)
【题目描述】
小杨在二维空间中有n nn个水平挡板，并且挡板之间彼此不重叠，其中第i ii个挡板处于水平高度h i h_ihi，左右端点分别位于l i l_ili与r i r_iri。
小杨可以在挡板上左右移动，当小杨移动到右端点时，如果再向右移动会竖直掉落，从而落到下方第一个挡板上， 移动到左端点时同理。小杨在挡板上每移动1 11个单位长度会耗费1 11个单位时间，掉落时每掉落1 11个单位高度也会耗费1 11个单位时间。
小杨想知道，从第s ss个挡板上的左端点出发到第t tt个挡板需要耗费的最少时间是多少？
注意：可能无法从第s ss个挡板到达到第t tt个挡板。
【输入】
第一行包含一个正整数n nn，代表挡板数量。
第二行包含两个正整数s , t s,ts,t，含义如题面所示。
之后n nn行，每行包含三个正整数l i , r i , h i l_i,r_i,h_ili,ri,hi，代表第i ii个挡板的左右端点位置与高度。
【输出】
输出一个整数代表需要耗费的最少时间，如果无法到达则输出− 1 -1−1。
【输入样例】
3 3 1 5 6 3 3 5 6 1 4 100000【输出样例】
100001【算法标签】
《洛谷 P10726 空间跳跃》 #动规规划DP# #最短路# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;structNode{intid;// 平台编号intl,r;// 平台左右端点inth;// 平台高度}a[1005];// 平台数组intn,s,t;// n: 平台数量, s: 起点平台编号, t: 终点平台编号intdp[1005][2];// dp[i][0]: 到达平台i左端点的最小时间// dp[i][1]: 到达平台i右端点的最小时间// 排序比较函数：按高度从高到低排序boolcmp(Node x,Node y){returnx.h>y.h;}intmain(){// 读入数据cin>>n>>s>>t;for(inti=1;i<=n;i++){cin>>a[i].l>>a[i].r>>a[i].h;a[i].id=i;// 记录原始编号}// 检查合法性if(a[s].h<a[t].h)// 起点高度必须不低于终点{cout<<-1<<endl;return0;}elseif(s==t)// 起点和终点相同{cout<<0<<endl;return0;}// 按高度从高到低排序sort(a+1,a+n+1,cmp);// 找到排序后起点和终点的位置intk=1;while(a[k].id!=s){k++;}s=k;// 更新起点在排序后数组中的位置k=1;while(a[k].id!=t){k++;}t=k;// 更新终点在排序后数组中的位置// 初始化DP数组为无穷大memset(dp,0x3f,sizeof(dp));// 初始化起点dp[s][0]=0;// 在起点平台左端点dp[s][1]=a[s].r-a[s].l;// 在起点平台右端点，需要横向走过去// 动态规划：从高到低处理平台for(inti=s;i<t;i++)// i: 当前平台{// 情况1：从当前平台i的左端点下落for(intj=i+1;j<=t;j++)// j: 下方平台{// 检查是否能落到平台j上（当前平台左端点垂直下方在平台j范围内）if(a[i].l>=a[j].l&&a[i].l<=a[j].r){if(j!=t)// 如果不是终点平台{// 到达平台j左端点的最小时间dp[j][0]=min(dp[j][0],dp[i][0]+(a[i].h-a[j].h)+(a[i].l-a[j].l));// 到达平台j右端点的最小时间dp[j][1]=min(dp[j][1],dp[i][0]+(a[i].h-a[j].h)+(a[j].r-a[i].l));}else// 如果是终点平台{// 只需要到达左端点（到达终点即可）dp[j][0]=min(dp[j][0],dp[i][0]+(a[i].h-a[j].h));}break;// 只能落到第一个遇到的平台上}}// 情况2：从当前平台i的右端点下落for(intj=i+1;j<=t;j++)// j: 下方平台{// 检查是否能落到平台j上（当前平台右端点垂直下方在平台j范围内）if(a[i].r>=a[j].l&&a[i].r<=a[j].r){if(j!=t)// 如果不是终点平台{// 到达平台j左端点的最小时间dp[j][0]=min(dp[j][0],dp[i][1]+(a[i].h-a[j].h)+(a[i].r-a[j].l));// 到达平台j右端点的最小时间dp[j][1]=min(dp[j][1],dp[i][1]+(a[i].h-a[j].h)+(a[j].r-a[i].r));}else// 如果是终点平台{// 只需要到达左端点（到达终点即可）dp[j][0]=min(dp[j][0],dp[i][1]+(a[i].h-a[j].h));}break;// 只能落到第一个遇到的平台上}}}// 输出结果if(dp[t][0]==0x3f3f3f3f)// 无法到达终点{cout<<-1<<endl;}else{cout<<min(dp[t][0],dp[t][1])<<endl;// 取到达终点左端点或右端点的最小值}return0;}【运行结果】
3 3 1 5 6 3 3 5 6 1 4 100000 100001
