三、动态规划（1）-Help Jimmy(POJ1661)

#include "stdafx.h"
#include <iostream>
#include<algorithm>
#include<string>
using namespace std;


#define MAX_N 1000
#define INFINITE 1000000

int t, n, x, y, maxHeight;  //组数，平台数，坐标x,y和最大下落高度
struct  Platform
{
    int Lx, Rx, h;
    bool operator<(const Platform& p2)const{//从高到第排序
        return h>p2.h;
    }

};

Platform platform[MAX_N+10];
int leftMinTime[MAX_N + 10];     //个板子从左走最短的时间
int rightMinTime[MAX_N +10]; // 各个板子从右边走最短的时间


int main(){
    cout << "输入组数：";
    cin >> t;
    cout << endl;
    while (t--){
        cout << "输入平台数n，坐标x,y, 最大下落高度：h:" << endl;
        cin >> n >> x >> y >> maxHeight;
        platform[0].Lx = x; platform[0].Rx = x; platform[0].h = y;  //初始位置

        for (int j = 1; j <= n; ++j)
            cin >> platform[j].Lx >> platform[j].Rx >> platform[j].h;

    //重新排序
        sort(platform,platform+n+1);
        cout << "---------排序队列--------------" << endl;
        for (int i = 0; i <= n; ++i){
            cout <<i<<" : "<< platform[i].Lx << " " << platform[i].Rx << " " << platform[i].h << endl;
        }
        cout << "---------结果--------------" << endl;

        //从下网上寻找
        for (int i = n; i >= 0; --i){
            int j;
            //寻找i的左端下面的板子
            for (j = i + 1; j <= n; ++j){   
                if (platform[i].Lx <=platform[j].Rx&&platform[i].Lx >= platform[j].Lx)
                    break;
            }
            if (j > n){//说明i的左下端不存在板子,下面是地板
                    if (platform[i].h > maxHeight)
                        leftMinTime[i] = INFINITE;
                    else
                    {
                        leftMinTime[i] = platform[i].h;
                    }
            }
            else
            {
                int h = platform[i].h - platform[j].h;
                if (h > maxHeight)
                    leftMinTime[i] = INFINITE;
                else
                    leftMinTime[i] = h +
                        min(leftMinTime[j] + platform[i].Lx - platform[j].Lx,
                                    rightMinTime[j] + platform[j].Rx - platform[i].Lx);
            }

            //寻找i的右端的下面的板子
            for (j = i + 1; j <= n; ++j){
                if (platform[i].Rx <= platform[j].Rx&&platform[i].Rx >= platform[j].Lx)
                    break;
            }
            if (j > n){// 没找到下方板子
                if (platform[i].h > maxHeight){
                    rightMinTime[i]= INFINITE;
                }
                else
                {
                    rightMinTime[i] = platform[i].h;
                }
            }
            else{
                int h = platform[i].h - platform[j].h;
                if (h > maxHeight)
                    rightMinTime[i] = INFINITE;
                else
                    rightMinTime[i] = h +
                    min(rightMinTime[j] + platform[j].Rx - platform[i].Rx,
                    leftMinTime[j] + platform[i].Rx - platform[j].Lx);
            }
        }

        cout << "最小时间为：" << min(leftMinTime[0], rightMinTime[0]) << endl;

    }
    return 0;

}