题目描述：

场景中包括多个长度和高度各不相同的平台，地面是最低的平台，高度为零，长度无限，Jimmy老鼠在时刻 0 从高于所有平台的某处开始下落，它的下落速度始终为1米/秒，当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒，当Jimmy跑到平台的边缘时，开始继续下落，Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束，设计一个程序，计算Jimmy到底地面时的最早时间

输入

第一行是测试数据的组数 t（0 <= t <= 20）
每组测试数据的第一行是四个整数 N，X，Y，MAX，用空格分隔
N是平台的数目（不包括地面）
X 和 Y 是Jimmy开始下落的位置的横竖坐标
MAX是一次下落的最大高度
接下来的N行每行描述一个平台，包括三个整数，X1[ i ]，X2[ i ] 和 H[ i ]
H[ i ]表示平台的高度
X1[ i ] 和 X2[ i ]表示平台左右端点的横坐标
1 <= N <= 1000，-20000 <= X，X1[i]， X2[i] <= 20000，0 < H[i] < Y <= 20000（i = 1..N）
补充：所有坐标的单位都是米，Jimmy的大小和平台的厚度均忽略不计，如果Jimmy恰好落在某个平台的边缘，被视为落在平台上，所有的平台均不重叠或相连，测试数据保证问题一定有解

输出

对输入的每组测试数据，输出一个整数，Jimmy到达地面时的最早时间

Example

Input
1
3 8 17 20
0 10 8
0 10 13
4 14 3

Output
23

正确代码

#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <queue>
#include <stack>
#include <map>  
#include <set>

#define _for(i,a,b) for(int i=a;i<b;i++)
#define _unfor(i,a,b) for(int i=a;i>=b;i--)
#define RI(a) scanf("%d",&a)
#define mset(a,val,n) for(int i=0;i<n;i++)a[i]=val;
#define mset2(a,val,n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=val;
#define FI freopen("D:\\in.txt","r",stdin)
#define FO freopen("D:\\out.txt","w",stdout)

using namespace std;
typedef long long LL;
/*-------下面为主要代码-------*/
 
const int N=1005;
const int M=20005;
 
struct Time  //定义结构体
{
    int x1,x2,h;
}a[N];
 
int dp[N+2][2]; // 0：表示第i的木板左边到底部的最短时间
              // 1: 表示第i的木板右边到底部的最短时间
 
int n,x,y,max_h;
 
int cmp(Time c,Time b) //排序函数
{
    return c.h > b.h; //从大到小排列
}
 
void left(int i) //左
{
    //如果平台i下面有平台，且两者相距不超过MAX
    int k = i+1;
    while( k<n+1 && a[i].h-a[k].h<=max_h ) //n+1处是地面
    {
        //确保平台k在平台i的左下方，且小鼠可以跳到上面
        if(a[i].x1 >= a[k].x1 && a[i].x1 <= a[k].x2)
        {
            //核心
            dp[i][0] = a[i].h-a[k].h + min(dp[k][0] + a[i].x1-a[k].x1 , dp[k][1]+a[k].x2-a[i].x1);
            return; //千万不要忘记:易错点+难点
        }
        k++;
    }
 
    if(a[i].h-a[k].h>max_h) //因为第二个条件出的循环即：不能到达下一平台
        dp[i][0]=INT_MAX;
    else  //这里的else是最有灵魂的地方：成败都在这
        dp[i][0]=a[i].h; //因为它下面没木板，直接落地
}
 
void right(int i)//右
{
    //如果平台i下面有平台，且两者相距不超过MAX
    int k=i+1;
    while(k<n+1 && a[i].h-a[k].h<=max_h)
    {
        //确保平台k在平台i的右下方，且小鼠可以跳到上面
        if(a[i].x2<=a[k].x2 && a[i].x2 >= a[k].x1)
        {
            dp[i][1]=a[i].h-a[k].h+min(dp[k][0] + a[i].x2-a[k].x1  ,  dp[k][1] + a[k].x2-a[i].x2);
            return;
        }
        k++;
    }
    if(a[i].h-a[k].h > max_h)//不能到达下一平台
        dp[i][1]=INT_MAX;
    else
        dp[i][1]=a[i].h; //因为它下面没木板，直接落地
}
 
int main()
{
    int t,i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&n,&x,&y,&max_h);//木板个数、老鼠的初始坐标、最大跳跃高度
 
        //地面也当做一块木板
        a[0].x1=-20000;
        a[0].x2=20000;
        a[0].h=0;
        //老鼠初始位置也当做一块木板
        a[1].x1=x;
        a[1].x2=x;
        a[1].h=y;
 
        for(i=2;i<=n+1;i++) //输入数据
            scanf("%d%d%d",&a[i].x1,&a[i].x2,&a[i].h);
 
        sort(a,a+n+2,cmp);  // 排序：一定要把sort用好
        memset(dp,0,sizeof(dp)); //初始化
 
        //为什么i是从n开始的呢？毋庸置疑n+1处是小鼠最初的位置往左往右都是0
        for(i=n; i>=0 ;i--)
        {
            left(i);//进行左：去bfs
            right(i);//进行右：去bfs
        }
        int time=min(dp[0][0],dp[0][1]); //取最小值
        printf("%d\n",time); //输出结果
    }
    return 0;
}

下面是我自己写了半天还没通过的代码，别参考了，别看了

解析

代码的简洁程度取决于对题目的理解程度，下面我说一些对本题的理解

1、场景中包括多个长度和高度各不相同的板子（平台），说明所有板子都是上下参差不齐的，写代码时不用考虑同一平面优先到哪一块板子，只用考虑不同高度优先下降到哪一块板子

2、贪心思路：下降到距离差更大的板子，这咋一看没问题，但这只是当前状态最优解，而不是整体最优解（如下图，明显第一条路是最优解）

3、采用下降一层回头看一层的策略，由下图距离

从三层出发，到二层，回头看第三层，可以算出时间是二、三层高度差 + 三层左侧距离（设为 t1），再到一层，回头看第二层和第三层，第一种时间是 t1 + 二层右侧距离 + 一二层高度差，第二种时间是一层右侧距离+一三层高度差，最后取最小就得出到达第一层所用时间的最优解

那么我们可以类比一下，若有很多层，每一层的时间就为 t + 回头看的层数左或右侧距离 + 回头看的层数与本层数高度差，而 t 即回头看的那层到最顶层所用的最优时间，再取最小值，因此这样就可以得出到达最底层所用时间的最优解

代码（别参考，没通过）

#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <queue>
#include <stack>
#include <map>  
#include <set>

#define _for(i,a,b) for(int i=a;i<b;i++)
#define _unfor(i,a,b) for(int i=a;i>=b;i--)
#define RI(a) scanf("%d",&a)
#define mset(a,val,n) for(int i=0;i<n;i++)a[i]=val;
#define mset2(a,val,n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=val;
#define FI freopen("D:\\in.txt","r",stdin)
#define FO freopen("D:\\out.txt","w",stdout)

using namespace std;
typedef long long LL;
/*-------下面为主要代码-------*/

const int N=1005; //最大层数 
const int M=20005; //绝对值最大坐标 

struct Time
{
    int x1,x2,h; //x1是左侧坐标,x2是右侧坐标,h是本层高度 
}a[N]; //N层板子 
 
int dp[N]; //代表当前当前层到最顶层的最短时间 
 
int n,x,y,max_h;
 
int cmp(Time c,Time b) //排序函数
{
    return c.h > b.h; //从大到小排列
}
 
void back(int i)
{
    int k = i+1;
    int tmp1,tmp2;
    while( k<=n+1 && a[k].h-a[i].h<=max_h ) //回头看上一层 
    {
        if(a[k].x1 >= a[i].x1 && a[k].x1 <= a[i].x2) 
        {
            //上一层左侧到这一层左侧的最短时间
            tmp1 = dp[k] + (a[k].x1 - a[i].x1) + (a[i].h - a[k].h);
        }
        if(a[k].x2 >= a[i].x1 && a[k].x2 <= a[i].x2)
        {
            //上一层右侧到这一层右侧的最短时间
            tmp2 = dp[k] + (a[i].x2 - a[k].x1) + (a[i].h - a[k].h);
        }
        if(i==0)
        {
        	tmp1-=a[k].x1 - a[i].x1;
        	tmp2-=a[i].x2 - a[k].x1;
		}
        dp[i] = max(tmp1,tmp2);
        k++; //再回头看上一层
    }
}
 
int main()
{
    int t; //t代表测试组数 
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&n,&x,&y,&max_h);//木板个数、老鼠的初始坐标、最大跳跃高度
 
        //地面也当做一块木板
        a[0].x1=-20000;
        a[0].x2=20000;
        a[0].h=0;
        //老鼠初始位置也当做一块木板
        a[n+1].x1=x;
        a[n+1].x2=x;
        a[n+1].h=y;
 
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&a[i].x1,&a[i].x2,&a[i].h);
 
        sort(a,a+n+1,cmp);
        mset(dp,0,sizeof(dp));
 
		for(int i=n; i>=0 ;i--)
        {
            back(i);
        }
        printf("%d\n",dp[0]);
    }
    return 0;
}