原题链接
题意：Jimmy要从最高点到达地面，他下落与在板上行走的速度都是1单位/s，到达下面的板子需要垂直下落，若下落高度大于M则他会摔死，现在给出N块板子，求Jimmy到达地面的最短时间。
思路：
d[i][j] (i:0~N+1, j:0~1)：
表示位于第i块板子的对应位置时下落到地面的最短时间。其中当j=0，表示在第i块板子最左边；当j=1，表示在第i块板子最右边。
第0块板子为地面；第N+1块板子代表起始位置，高度为起始高度，左右边界均为起始横坐标（即板子长度为0）。
状态转移：
设当前位置为p（x，y），在p下方的第一个板子为k（在下方即：k左边界<=x<=k右边界）。
若p与k间垂直距离不大于M（y-k的高度）则有两种决策，落下到k后，到k的左边界或右边界。
若p与k间垂直距离大于M，则不存在合法距离，当前d值为INF。
边界条件：
当k为第0块板子，即地面时，不计算到达左边界或右边界的花费，因为为满足条件，地面的左右边界都应设为极限值。
代码：
#include <iostream> #include <algorithm> using namespace std; const int INF=0x3f3f3f3f; int N,X,Y,M,T,d[1010][2]; struct Floor{ int l,r,h; bool operator<(Floor a){return h<a.h;} }; Floor f[1010]; int main(){ cin>>T; while(T--){ cin>>N>>X>>Y>>M; for(int i=1;i<=N;i++){ int a,b,c; cin>>a>>b>>c; f[i].l=a,f[i].r=b,f[i].h=c; } sort(f+1,f+N+1); f[N+1].l=X,f[N+1].r=X,f[N+1].h=Y; f[0].l=-20010,f[0].r=20010,f[0].h=0; for(int i=1;i<=N+1;i++) for(int j=0;j<2;j++){ int x=j?f[i].r:f[i].l; d[i][j]=INF; for(int k=i-1;k>=0;k--){ int l=f[k].l,r=f[k].r,dh=f[i].h-f[k].h; if(dh>M) break; if(x>=l&&x<=r){ int dl=k?x-l:0,dr=k?r-x:0; d[i][j]=min(d[k][0]+dl,d[k][1]+dr)+dh; break; } } if(i==N+1) break; } cout<<d[N+1][0]<<endl; } return 0; }