POJ - 1661 Help Jimmy(DP)

题目大意：中文题

解题思路：因为是垂直下降，所以就可以将问题转变成从降落的平台到地面的最小时间
因为只能从平台的左边或者右边才可以离开平台，所以可以分别计算出从左边和从右边到达地面的最短时间，并记录

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010;
const int INF = 0x3f3f3f3f;

struct Board{
    int x, y, h;
}B[N];

int n, Max;
int L[N], R[N];

int cmp(const Board &a, const Board &b) {
    return a.h > b.h;
}

void init() {
    scanf("%d%d%d%d", &n, &B[0].x, &B[0].h, &Max)   ;
    B[0].y = B[0].x;

    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &B[i].x, &B[i].y, &B[i].h);
    sort(B, B + n + 1, cmp);
    memset(L, -1, sizeof(L));
    memset(R, -1, sizeof(R));
}

int dfs(int cur, int dir) {
    int x, h;
    h = B[cur].h;
    if (dir == 0)  x = B[cur].x;
    else x = B[cur].y;

    int find = -1;
    for (int i = cur + 1; i <= n; i++) {
        if (B[i].x <= x && B[i].y >= x ) {
            find = i;
            break;
        }
    }

    if (find == -1) {
        if (h > Max) return INF;
        else return h;
    }
    else if(h - B[find].h > Max) return INF;

    int leftTime = h - B[find].h + x - B[find].x;
    int rightTime = h - B[find].h + B[find].y - x;
    if (L[find] == -1)
        L[find] = dfs(find, 0);
    if (R[find] == -1)
        R[find] = dfs(find, 1);

    leftTime += L[find];
    rightTime += R[find];
    return leftTime < rightTime ? leftTime: rightTime;
}

int main() {
    int test;
    scanf("%d", &test);
    while (test--) {
        init();
        printf("%d\n", dfs(0, 0));
    }
    return 0;
}