动态规划3--Help Jimmy
一、心得
二、题目
三、分析
Jimmy跳到一块板上后，可以有两种选择，向左走，或向右走。
走到左端和走到右端所需的时间，是很容易算的。
如果我们能知道，以左端为起点到达地面的最短时间，和以右端为起点到达地面的最短时间，那么向左走还是向右走，就很容选择了。
因此，整个问题就被分解成两个子问题，即Jimmy所在位置下方第一块板左端为起点到地面的最短时间，和右端为起点到地面的最短时间。
这两个子问题在形式上和原问题是完全一致的。将板子从上到下从1开始进行无重复的编号(越高的板子编号越小，高度相同的几块板子，哪块编号在前无所谓)，那么，和上面两个子问题相关的变量就只有板子的编号。
将板子由高到低按从0到n编号，起始点的为0
不妨认为Jimmy开始的位置是一个编号为0，长度为0的板子
设LeftMinTime(k)表示从k号板子左端到地面的最短时间
RightMinTime(k)表示从k号板子右端到地面的最短时间
if ( 板子k左端正下方没有别的板子) {
if( 板子k的高度 h(k) 大于Max)
LeftMinTime(k) = ∞;
else
LeftMinTime(k) = h(k);
}
else if( 板子k左端正下方的板子编号是m )
LeftMinTime(k) = h(k)-h(m) +
Min( LeftMinTime(m) + Lx(k)-Lx(m),
RightMinTime(m) + Rx(m)-Lx(k));
}
上面，h(i)就代表i号板子的高度，Lx(i)就代表i号板子左端点的横坐标，Rx(i)就代表i号板子右端点的横坐标。那么 h(k)-h(m) 当然就是从k号板子跳到m号板子所需要的时间，Lx(k)-Lx(m) 就是从m号板子的落脚点走到m号板子左端点的时间，Rx(m)-Lx(k)就是从m号板子的落脚点走到右端点所需的时间。
求RightMinTime(k)的过程类似。
不妨认为Jimmy开始的位置是一个编号为0，长度为0的板子，那么整个问题就是要求LeftMinTime(0)。
输入数据中，板子并没有按高度排序，所以程序中一定要首先将板子排序。
时间复杂度： 一共 n个板子，每个左右两端的最小时间各算一次 O(n) 找出板子一段到地面之间有那块板子，需要遍历板子 O(n) 总的时间复杂度O(n2)
四、代码及结果
1、记忆化递归
/*
POJ1661 Help Himmy
这样效率太低了，一早上没看几个题
代码要是不是特别好看懂，先把伪代码写出来就比较好懂了 分析：
将板子由高到低按从0到n编号，起始点的为0
不妨认为Jimmy开始的位置是一个编号为0，长度为0的板子
设LeftMinTime(k)表示从k号板子左端到地面的最短时间
RightMinTime(k)表示从k号板子右端到地面的最短时间
if ( 板子k左端正下方没有别的板子) {
if( 板子k的高度 h(k) 大于Max)
LeftMinTime(k) = ∞;
else
LeftMinTime(k) = h(k);
}
else if( 板子k左端正下方的板子编号是m )
LeftMinTime(k) = h(k)-h(m) +
Min( LeftMinTime(m) + Lx(k)-Lx(m),
RightMinTime(m) + Rx(m)-Lx(k));
}
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAX_N 1000
#define INFINITE 1000000
int t,n,x,y,maxHeight;
struct Platform{//定义平台结构体
int Lx, Rx, h;//Lx表示做边界横坐标，Rx表示右边界横坐标，h表示高度
bool operator < (const Platform & p2) const {//符号重载，sort的时候能按h从高到低排
return h > p2.h;
}
};
Platform platForms[MAX_N + ];//平台
int leftMinTime[MAX_N + ];//走左边的最小时间
int rightMinTime[MAX_N + ];//走右边的最小时间
int L[MAX_N + ];//
//l表示现在这块板的编号，越在上面的编号越小，bleft表示是否向左边走
//因为这题分为向左和向右两种情况
int MinTime( int l, bool bLeft )//l表示现在这块板的编号，越在上面的编号越小，bleft表示是否向左边走
{
//初始化x和y坐标，如果是去左边，就走到左边边上，如果去右边，就走到右边边上
int y = platForms[l].h;
int x;
//如果是去左边，就走到左边边上，如果去右边，就走到右边边上
if(bLeft)
x = platForms[l].Lx;
else
x = platForms[l].Rx;
int i;
for( i = l + ;i <= n;i ++ ) {//找到现在这块板下面的那块板
if( platForms[i].Lx <= x && platForms[i].Rx >= x)//判断从当前条能跳到的小一块板子上
break;
}
if( i <= n ) {// 板子k左端正下方有别的板
if( y - platForms[i].h > maxHeight )// 跳到这块平台的高度如果大于Max
return INFINITE;//返回无限大
}
else {// 板子k左端正下方没有别的板
if( y > maxHeight )//板子k的高度 h(k) 大于Max
return INFINITE;//返回无限大
else
return y;//如果可以直接跳下，就输出y
}
int nLeftTime = y - platForms[i].h + x - platForms[i].Lx;//现在平台与下一块平台的高度差以及下一块平台左边界的距离
int nRightTime = y - platForms[i].h + platForms[i].Rx - x;//现在平台与下一块平台的高度差以及下一块平台右边界的距离
if( leftMinTime[i] == - ) //等于-1表示我初始化过 ，如果还可以向左我们就向左
leftMinTime[i] = MinTime(i,true);//向左进入子问题
if( L[i] == - )//等于-1表示我初始化过 ，如果还可以向右我们就向右
L[i] = MinTime(i,false);//像右进入子问题
nLeftTime += leftMinTime[i];//左边固定花费的时间加上下一场左边这样的时间
nRightTime += L[i];//右边固定花费的时间加上下一场右边这样的时间
//返回左边和右边走中值小的那一个
if( nLeftTime < nRightTime )
return nLeftTime;
return nRightTime;
} int main() {
freopen("in.txt","r",stdin);
scanf("%d",&t);//读入t组数据
for( int i = ;i < t; i ++ ) {//对每组数据进行操作
memset(leftMinTime,-,sizeof(leftMinTime));//初始化leftMinTime
memset(L,-,sizeof(rightMinTime));//初始化L
scanf("%d%d%d%d",&n, &x, &y, &maxHeight);//读入数据
platForms[].Lx = x; platForms[].Rx = x;
platForms[].h = y;//起始点初始化
for( int j = ; j <= n; j ++ )//读入平台信息
scanf("%d%d%d",&platForms[j].Lx,& platForms[j].Rx, & platForms[j].h);
sort(platForms,platForms+n+);//对平台由高到低排序
printf("%d\n", MinTime(,true));//MinTime()方法求下平台的最小时间
}
return ;
}
