学步园

Description
“Help Jimmy” 是在下图所示的场景上完成的游戏。

场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。

Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。

设计一个程序，计算Jimmy到底地面时可能的最早时间。

Input
第一行是测试数据的组数t（0 <= t <= 20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N是平台的数目（不包括地面），X和Y是Jimmy开始下落的位置的横竖坐标，MAX是一次下落的最大高度。接下来的N行每行描述一个平台，包括三个整数，X1[i]，X2[i]和H[i]。H[i]表示平台的高度，X1[i]和X2[i]表示平台左右端点的横坐标。1 <= N <= 1000，-20000 <= X, X1[i], X2[i] <= 20000，0 < H[i] < Y <= 20000（i = 1..N）。所有坐标的单位都是米。

Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保证问题一定有解。

Output
对输入的每组测试数据，输出一个整数，Jimmy到底地面时可能的最早时间。

Sample Input

1
3 8 17 20
0 10 8
0 10 13
4 14 3

Sample Output

23

Source
POJ Monthly–2004.05.15 CEOI 2000

简单的dp题，但是很坑

/*************************************************************************
    > File Name: dp12.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年02月12日 星期四 21时23分29秒
 ************************************************************************/

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;

const int N = 1010;
int dp[N][2]; 

int x, y, ma, n;
struct node
{
    int l, r, h;
}tai[N];

int cmp (node a, node b)
{
    return a.h > b.h;
}

int main ()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d%d%d", &n, &x, &y, &ma);
        memset (dp, inf, sizeof(dp));
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d%d%d", &tai[i].l, &tai[i].r, &tai[i].h);
        }
        tai[n + 1].l = -21000;
        tai[n + 1].r = 21000;
        tai[n + 1].h = 0;
        sort (tai + 1, tai + n + 2, cmp);
        dp[n + 1][0] = 0;
        dp[n + 1][1] = 0;
        int s;
        for (int i = 1; i <= n + 1; ++i)
        {
            if (tai[i].l <= x && x <= tai[i].r && y - tai[i].h <= ma)
            {
                s = i;
                break;
            }
        }
        for (int i = n; i >= s; --i)
        {
            for (int j = i + 1; j <= n + 1; ++j)
            {
                //左：
                if (tai[i].l >= tai[j].l && tai[i].l <= tai[j].r && tai[i].h - tai[j].h <= ma)
                {
                    if (j != n + 1)
                    {
                        dp[i][0] = min (dp[j][0] + tai[i].l - tai[j].l, dp[j][1] + tai[j].r - tai[i].l) + tai[i].h - tai[j].h;
                    }
                    else
                    {
                        dp[i][0] = tai[i].h;
                    }
                    break;
                }
            }
            for (int j = i + 1; j <= n + 1; ++j)
            {
                if (tai[i].r >= tai[j].l && tai[i].r <= tai[j].r && tai[i].h - tai[j].h <= ma)
                {
                    if (j != n + 1)
                    {
                        dp[i][1] = min (dp[j][0] + tai[i].r - tai[j].l, dp[j][1] + tai[j].r - tai[i].r) + tai[i].h - tai[j].h;
                    }
                    else
                    {
                        dp[i][1] = tai[i].h;
                    }
                    break;
                }
            }
        }
        int ans;
        if (s != n + 1)
        {
            ans = min (dp[s][0] + x - tai[s].l, dp[s][1] + tai[s].r - x) + y - tai[s].h;
        }
        else
        {
            ans = y - tai[s].h;
        }
        printf("%d\n", ans);
    }
    return 0;
}