题目链接：http://poj.org/problem?id=1661
解题思路：
离散化处理 + DP。
首先，纵坐标除了用来判断老鼠是否会摔死之外基本没用，主要考虑横坐标，只要求出在横坐标上必须走的最短距离，加上题目给出的Y就是答案了。由题目知-20000 <= X, X1[i], X2[i] <= 20000，为了方便后面的处理，我们把这三个数据统一加上20000，不让他出现负数。
接下来介绍DP的思路，dp[i][x]——代表走到第 i 个平台的横坐标为 x 的点所需走过的最短距离（这里的距离其实都只是考虑横坐标上的距离，不考虑纵坐标，下面的讨论也一样），但是 1 <= N <= 1000 和 x 数据范围显然不允许我们开出这么大的数组，因此我们可以用离散化的技巧，把 x 的数据范围缩小为 [0,2000]，这样就勉强可以开出数组了。我们先把平台按照高度由高到低的顺序排好序，则 dp[i][x] = min(dp[i][x] , dp[j][第 j 个平台的左端点坐标]（条件：老鼠从第 j 个平台掉到第 i 个平台不会掉死并且这两点之间没有其他平台，右端点一样）, dp[j][第 j 个平台的右端点坐标]）（j 是从老鼠掉下来的第一个平板到第 i 个平板之间的所有平板）。
具体细节请看代码。
AC代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 const int maxn=1000+5,inf=0x7ffffff; 7 struct node{ 8 int x1,x2,h; 9 }plat[maxn]; 10 bool cmp(node &a, node &b){ 11 return a.h>b.h; 12 } 13 int dp[maxn][maxn<<1]; 14 int xs[maxn<<1],x_on[40004]; 15 int vis[maxn][2]; //0，左端点；1，右端点。这个vis数组是重点，标记第i个平台的左右端点是否已经处理过了 16 int main(){ 17 int t,X,Y,N,MAX; 18 scanf("%d",&t); 19 while(t--){ 20 memset(vis,0,sizeof(vis)); 21 memset(x_on,-1,sizeof(x_on)); 22 scanf("%d%d%d%d",&N,&X,&Y,&MAX); 23 X+=20000; //记得X也要加20000 24 int x_num=0; 25 for(int i=0;i<N;i++){ 26 scanf("%d%d%d",&plat[i].x1,&plat[i].x2,&plat[i].h); 27 plat[i].x1+=20000, plat[i].x2+=20000; 28 29 //离散化 30 //******************************************************************* 31 if(x_on[plat[i].x1]==-1){ 32 x_on[plat[i].x1]=x_num; xs[x_num++]=plat[i].x1; 33 } 34 if(x_on[plat[i].x2]==-1){ 35 x_on[plat[i].x2]=x_num; xs[x_num++]=plat[i].x2; 36 } 37 } 38 sort(xs,xs+x_num); 39 for(int i=0;i<x_num;i++) 40 x_on[xs[i]]=i; 41 //******************************************************************** 42 43 int newx; 44 sort(plat,plat+N,cmp); 45 46 int start; 47 for(start=0;start<N;start++){ 48 if(plat[start].x1<=X&&plat[start].x2>=X) 49 break; 50 vis[start][0]=vis[start][1]=1; 51 } //找出老鼠落下的第一个平台，上面的平台不会再用到了，我们随手处理一下访问标记 52 53 if(start==N){ //老鼠直接掉到地上的情况也不能忘了考虑哦 54 printf("%d ",Y); 55 continue; 56 } 57 58 for(int i=0;i<N;i++){ 59 for(int j=0;j<x_num;j++) dp[i][j]=inf; 60 } 61 newx=x_on[plat[start].x1]; 62 dp[start][newx]=X-plat[start].x1; 63 newx=x_on[plat[start].x2]; 64 dp[start][newx]=plat[start].x2-X; 65 for(int i=start+1;i<N;i++){ 66 int l=plat[i].x1,r=plat[i].x2,h=plat[i].h; 67 for(int j=start;j<i;j++){ 68 //如果第j个平台的端点已经被访问了，即对应的vis数组为1，就说明在这个端点到第i个平台之间有平台阻挡 69 if(vis[j][0]&&vis[j][1]) continue; 70 if(plat[j].h-h>MAX) continue; 71 72 if(!vis[j][0]&&plat[j].x1<=r&&plat[j].x1>=l){ 73 vis[j][0]=1; 74 dp[i][x_on[l]]=min(dp[i][x_on[l]],dp[j][x_on[plat[j].x1]]+plat[j].x1-l); 75 dp[i][x_on[r]]=min(dp[i][x_on[r]],dp[j][x_on[plat[j].x1]]+r-plat[j].x1); 76 } 77 if(!vis[j][1]&&plat[j].x2<=r&&plat[j].x2>=l){ 78 vis[j][1]=1; 79 dp[i][x_on[l]]=min(dp[i][x_on[l]],dp[j][x_on[plat[j].x2]]+plat[j].x2-l); 80 dp[i][x_on[r]]=min(dp[i][x_on[r]],dp[j][x_on[plat[j].x2]]+r-plat[j].x2); 81 } 82 } 83 } 84 int ans=inf; 85 for(int i=N-1;i>=start;i--){ 86 //从最后一个平台往前遍历，凡是vis标记为0的，即证明这一点没有被处理过，也就证明这一点到地面之间没有阻挡，那么可以从这一点直接跳到地面 87 if(plat[i].h>MAX) break; //遍历到高度大于MAX的平台就结束 88 if(!vis[i][0]) 89 ans=min(ans,dp[i][x_on[plat[i].x1]]); 90 if(!vis[i][1]) 91 ans=min(ans,dp[i][x_on[plat[i].x2]]); 92 } 93 printf("%d ",ans+Y); 94 } 95 return 0; 96 }