poj 1661 Help Jimmy(DP)

题意：从起点走到地面的最短时间

分析：每一层只能由上面的掉下来，可能是上面的任何一层，那么反过来，上面的每一层只能由左端或者右端往下掉，掉到下面的某一层的左右端点包含上面这一层的左端或者右端，那么将这n个台阶按照从下往上排序。

dp[i][0]表示从下面到达第i层的左端花费最短的时间，dp[i][1]表示从下面到达第i层的右端花费的最短的时间。

dp[i][0] = min(dp[L][0]+step[i].l-step[L].l, dp[L][1]+step[L].r-step[i].l)+step[i].h-step[L].h;

dp[i][1] = min(dp[R][0]+step[i].r-step[i].l, dp[R][1]+step[R].r-step[i].r)+step[i].h-step[R].h;

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <algorithm>

using namespace std;

const int oo = 1e9;

struct Step
{
    int l, r, h;
}step[2005];

bool cmp(Step a1, Step a2)
{
    return a1.h<a2.h;
}
int dp[2002][2];

int main()
{
    int t;
    int n, x, y, Max;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d%d", &n, &x, &y, &Max);
        step[0].l = step[0].r = x;
        step[0].h = y;
        dp[0][0] = dp[0][1] = oo;
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d%d", &step[i].l, &step[i].r, &step[i].h);
            dp[i][0]=oo;
            dp[i][1]=oo;
        }
        sort(step, step+n+1, cmp);
        int ls, rs;
        for(int i=0; i<=n; i++)
        {
            ls = rs = -1;
            for(int j=0; j<i; j++)
            {
                if(step[j].l<=step[i].l&&step[j].r>=step[i].l)
                    ls = j;
                if(step[j].l<=step[i].r&&step[j].r>=step[i].r)
                    rs = j;
            }
            if(ls==-1 && step[i].h<=Max)//直接从第i层跳到地面
                dp[i][0] = step[i].h;
            if(rs==-1 && step[i].h<=Max)//同上
                dp[i][1] = step[i].h;

            if(ls!=-1 && step[i].h - step[ls].h <= Max)
                dp[i][0] = min(dp[ls][0]+step[i].l-step[ls].l, dp[ls][1]+step[ls].r-step[i].l)+step[i].h-step[ls].h;

            if(rs!=-1 && step[i].h - step[rs].h <= Max)
                dp[i][1] = min(dp[rs][0]+step[i].r-step[rs].l, dp[rs][1]+step[rs].r-step[i].r)+step[i].h-step[rs].h;
        }

        printf("%d
", dp[n][0]);//dp[n][1]=dp[n][0]
    }

    return 0;
}