基础DP，过程想明白了其实也不复杂，从上面的推下面的比倒着推要简单很多。调试了半个多小时。。简单dp依然不能快速AC。。SAD。。

题目链接：

http://poj.org/problem?id=1661

题意：

Jimmy从坐标为x，高度为y的点向下跳，每次只能跳到平台上或者地面上，跳到平台上必须跑到平台边缘才能继续下跳。问最少多少时间跳到地面。

分析：

注意：

1. 对于每个平台左右两边都可以跳，需要分别记录最短时间。
2. 只能从平台直接跳到下面最近的平台，不能隔着平台跳到更下面的平台。

想明白了就很简单了。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define sa(a) scanf("%d", &a)

#define sal(a) scanf("%I64d", &a)

const int maxn = 1e3+ 5, INF = 0x3f3f3f3f;

struct DP {int x1; int x2; int h; int t1; int t2;};

DP dp[maxn];

bool cmp(DP a, DP b){return a.h > b.h;}

int main (void)

{

    int t;sa(t);

    while(t--){

        int n, x, y, MAX;

        sa(n), sa(x), sa(y), sa(MAX);

        for(int i = 1; i <= n; i++){

            sa(dp[i].x1), sa(dp[i].x2), sa(dp[i].h);

        }

        sort(dp + 1, dp + n + 1, cmp);

        for(int i = 1; i <= n; i++){

            dp[i].t1 = dp[i].t2 = INF;

        }

        dp[0].t1 = dp[0].t2 = 0;

        dp[0].h = y, dp[0].x1 = dp[0].x2 = x;

        int res = INF;

        for(int i = 0; i <= n; i++){

            bool flag = false;

            for(int j = i + 1; j <= n; j++){

               if(dp[i].x1 >= dp[j].x1 && dp[j].x2 >= dp[i].x1){

                    int cha = dp[i].h - dp[j].h;

                    if(cha == 0 || cha > MAX) continue;

                    dp[j].t1 = min(dp[j].t1, dp[i].t1 + cha + dp[i].x1 - dp[j].x1);

                    dp[j].t2 = min(dp[j].t2, dp[i].t1 + cha + dp[j].x2 - dp[i].x1);

                    flag = true;

               }

               if(flag) break;

            }

            bool flag2 = false;

            for(int j = i + 1; j <= n; j++){

               if(dp[i].x2 <= dp[j].x2 && dp[j].x1 <= dp[i].x2){

                    int cha = dp[i].h - dp[j].h;

                    if(cha == 0 || cha > MAX) continue;

                    dp[j].t1 = min(dp[j].t1, dp[i].t2 + cha + dp[i].x2 - dp[j].x1);

                    dp[j].t2 = min(dp[j].t2, dp[i].t2 + cha + dp[j].x2 - dp[i].x2);

                     flag2 = true;

               }

               if(flag2) break;

            }

            if(dp[i].h > MAX) continue;

            if(!flag)  res = min(res, dp[i].t1 + dp[i].h);

            if(!flag2) res = min(res, dp[i].t2 + dp[i].h);

        }

       printf("%d\n", res);

    }

    return 0;

}