Help Jimmy 心得+被坑之路

"Help Jimmy" 是在下图所示的场景上完成的游戏。
<center> </center>
场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。

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

这道题总的来说就是求最短路。

先说一下状态转移方程：

           左边最优：dp[i][0] = a[i].h-a[k].h + min(dp[k][0]+a[i].x1-a[k].x1 , dp[k][1]+a[k].x2-a[i].x1);

           右边最优：dp[i][1] = a[i].h-a[k].h + min(dp[k][0]+a[i].x2-a[k].x1 , dp[k][1]+a[k].x2-a[i].x2);

再说一下我遇到的坑点：

     1. 拿到题时就知道一定用dp，但是一开始设的是一维dp，觉得用一个状态来存上一个位置的最优解，后来发现根本做不了。

然后想到创建二维dp把状态一分二，如dp[i][0] 和 dp[i][1] 分别代表左边和右边落下的最优解。

     2.一开始写cmp时是按照递增排列的，即起点在dp[0][0]和dp[0][1]（特殊：在0的位置他们代表一个起点）。后来发现结果莫名为负数，很无奈emmm......2333，看了很多大神的代码后，发现他们都是降序排列，我发现的确简单很多，即写cmp时，

bool cmp(Pin a,Pin b){

        return a.h < b.h;

}

    3.我忘了把地面这一层加进去emmmmm。

最后上代码：

tip：代码较长，请耐心看。。。2333。

#include <iostream>
#include <string>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <set>
#include <sstream>
#include <map>
#include <cctype>

using namespace std;
#define Start clock_t start = clock();
#define End clock_t end = clock();
#define Print cout<<(double)(end-start)/CLOCKS_PER_SEC*1000<<"ºÁÃë"<<endl;

const int maxn = 10000 + 5;
int n,maxi;
struct Pin{
    int x1,x2;
    int h;
}a[maxn];
bool cmp(Pin a,Pin b){
    return a.h < b.h;
}
int dp[maxn][2];
//左边最优解
void ltime(int i){
    int k = i - 1;
    while(k > 0 && a[i].h - a[k].h <= maxi){//如果有板子，并且高度差在允许范围内，则必须跳到这个板子上
        if(a[i].x1 >= a[k].x1 && a[i].x1 <= a[k].x2){
             dp[i][0] = a[i].h-a[k].h + min(dp[k][0]+a[i].x1-a[k].x1 , dp[k][1]+a[k].x2-a[i].x1);
             return;//必须是左下方的第一个板子，找到就结束
        }
        else k--;
    }
    //这个板子左下面没有板子，那么看他与地面的距离
    if(a[i].h - a[k].h > maxi)//如果与地面的距离太大 ,返回一个很大的值，方便在比较中把它去掉
        dp[i][0] = 999999;
    else//如果可以直接跳到地上
        dp[i][0] = a[i].h - a[k].h;
}
//右边最优解
/*！！！！！！！！！！！！！请注意在求左边和右边时的a[i]与a[k]的x1和x2值，别写错了！！！！！！！！！！！！！*/
void rtime(int i){
    int k = i - 1;
    while(k > 0 && a[i].h - a[k].h <= maxi){//如果有板子，并且高度差在允许范围内，则必须跳到这个板子上
        if(a[i].x2 >= a[k].x1 && a[i].x2 <= a[k].x2){
             dp[i][1] = a[i].h-a[k].h + min(dp[k][0]+a[i].x2-a[k].x1 , dp[k][1]+a[k].x2-a[i].x2);
             return;//必须是右下方的第一个板子，找到就结束
        }
        else k--;
    }
    //这个板子左下面没有板子，那么看他与地面的距离
    if(a[i].h - a[k].h > maxi)//如果与地面的距离太大 ,返回一个很大的值，方便在比较中把它去掉
        dp[i][1] = 999999;
    else//如果可以直接跳到地上
        dp[i][1] = a[i].h - a[k].h;
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        cin>>n;//n个平台
        cin>>a[n+1].x1>>a[n+1].h>>maxi;//加上地面一共有n+1个平台（起点不算）
         //初始化地面和当前位置
        a[n+1].x2 = a[n+1].x1;
        a[0].x1 = 100000;
        a[0].x2 = -100000;
        a[0].h = 0;
         //读取n层平台
        for(int i = 1;i <= n;i++){
            cin>>a[i].x1>>a[i].x2>>a[i].h;
        }
        sort(a,a+n+1,cmp);//板子从低到高排序
        for(int i = 1;i <= n+1;i++){
            ltime(i);
            rtime(i);
        }
        int ans = min(dp[n+1][0],dp[n+1][1]);
        cout<<ans<<endl;
    }
    return 0;
}