动态规划3--Help Jimmy
一、心得
二、题目
三、分析
Jimmy跳到一块板上后，可以有两种选择，向左走，或向右走。
走到左端和走到右端所需的时间，是很容易算的。
如果我们能知道，以左端为起点到达地面的最短时间，和以右端为起点到达地面的最短时间，那么向左走还是向右走，就很容选择了。
因此，整个问题就被分解成两个子问题，即Jimmy所在位置下方第一块板左端为起点到地面的最短时间，和右端为起点到地面的最短时间。
这两个子问题在形式上和原问题是完全一致的。将板子从上到下从1开始进行无重复的编号(越高的板子编号越小，高度相同的几块板子，哪块编号在前无所谓)，那么，和上面两个子问题相关的变量就只有板子的编号。
将板子由高到低按从0到n编号，起始点的为0
不妨认为Jimmy开始的位置是一个编号为0，长度为0的板子
设LeftMinTime(k)表示从k号板子左端到地面的最短时间
RightMinTime(k)表示从k号板子右端到地面的最短时间
1 if ( 板子k左端正下方没有别的板子) { 2 if( 板子k的高度 h(k) 大于Max) 3 LeftMinTime(k) = ∞; 4 else 5 LeftMinTime(k) = h(k); 6 } 7 else if( 板子k左端正下方的板子编号是m ) 8 LeftMinTime(k) = h(k)-h(m) + 9 Min( LeftMinTime(m) + Lx(k)-Lx(m), 10 RightMinTime(m) + Rx(m)-Lx(k)); 11 }
上面，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、记忆化递归
1 /* 2 POJ1661 Help Himmy 3 这样效率太低了，一早上没看几个题 4 代码要是不是特别好看懂，先把伪代码写出来就比较好懂了 5 6 分析： 7 将板子由高到低按从0到n编号，起始点的为0 8 不妨认为Jimmy开始的位置是一个编号为0，长度为0的板子 9 设LeftMinTime(k)表示从k号板子左端到地面的最短时间 10 RightMinTime(k)表示从k号板子右端到地面的最短时间 11 if ( 板子k左端正下方没有别的板子) { 12 if( 板子k的高度 h(k) 大于Max) 13 LeftMinTime(k) = ∞; 14 else 15 LeftMinTime(k) = h(k); 16 } 17 else if( 板子k左端正下方的板子编号是m ) 18 LeftMinTime(k) = h(k)-h(m) + 19 Min( LeftMinTime(m) + Lx(k)-Lx(m), 20 RightMinTime(m) + Rx(m)-Lx(k)); 21 } 22 */ 23 #include <iostream> 24 #include <cstdio> 25 #include <algorithm> 26 #include <cstring> 27 using namespace std; 28 #define MAX_N 1000 29 #define INFINITE 1000000 30 int t,n,x,y,maxHeight; 31 struct Platform{//定义平台结构体 32 int Lx, Rx, h;//Lx表示做边界横坐标，Rx表示右边界横坐标，h表示高度 33 bool operator < (const Platform & p2) const {//符号重载，sort的时候能按h从高到低排 34 return h > p2.h; 35 } 36 }; 37 Platform platForms[MAX_N + 10];//平台 38 int leftMinTime[MAX_N + 10];//走左边的最小时间 39 int rightMinTime[MAX_N + 10];//走右边的最小时间 40 int L[MAX_N + 10];// 41 //l表示现在这块板的编号，越在上面的编号越小，bleft表示是否向左边走 42 //因为这题分为向左和向右两种情况 43 int MinTime( int l, bool bLeft )//l表示现在这块板的编号，越在上面的编号越小，bleft表示是否向左边走 44 { 45 //初始化x和y坐标，如果是去左边，就走到左边边上，如果去右边，就走到右边边上 46 int y = platForms[l].h; 47 int x; 48 //如果是去左边，就走到左边边上，如果去右边，就走到右边边上 49 if(bLeft) 50 x = platForms[l].Lx; 51 else 52 x = platForms[l].Rx; 53 int i; 54 for( i = l + 1;i <= n;i ++ ) {//找到现在这块板下面的那块板 55 if( platForms[i].Lx <= x && platForms[i].Rx >= x)//判断从当前条能跳到的小一块板子上 56 break; 57 } 58 if( i <= n ) {// 板子k左端正下方有别的板 59 if( y - platForms[i].h > maxHeight )// 跳到这块平台的高度如果大于Max 60 return INFINITE;//返回无限大 61 } 62 else {// 板子k左端正下方没有别的板 63 if( y > maxHeight )//板子k的高度 h(k) 大于Max 64 return INFINITE;//返回无限大 65 else 66 return y;//如果可以直接跳下，就输出y 67 } 68 int nLeftTime = y - platForms[i].h + x - platForms[i].Lx;//现在平台与下一块平台的高度差以及下一块平台左边界的距离 69 int nRightTime = y - platForms[i].h + platForms[i].Rx - x;//现在平台与下一块平台的高度差以及下一块平台右边界的距离 70 if( leftMinTime[i] == -1 ) //等于-1表示我初始化过 ，如果还可以向左我们就向左 71 leftMinTime[i] = MinTime(i,true);//向左进入子问题 72 if( L[i] == -1 )//等于-1表示我初始化过 ，如果还可以向右我们就向右 73 L[i] = MinTime(i,false);//像右进入子问题 74 nLeftTime += leftMinTime[i];//左边固定花费的时间加上下一场左边这样的时间 75 nRightTime += L[i];//右边固定花费的时间加上下一场右边这样的时间 76 //返回左边和右边走中值小的那一个 77 if( nLeftTime < nRightTime ) 78 return nLeftTime; 79 return nRightTime; 80 } 81 82 int main() { 83 freopen("in.txt","r",stdin); 84 scanf("%d",&t);//读入t组数据 85 for( int i = 0;i < t; i ++ ) {//对每组数据进行操作 86 memset(leftMinTime,-1,sizeof(leftMinTime));//初始化leftMinTime 87 memset(L,-1,sizeof(rightMinTime));//初始化L 88 scanf("%d%d%d%d",&n, &x, &y, &maxHeight);//读入数据 89 platForms[0].Lx = x; platForms[0].Rx = x; 90 platForms[0].h = y;//起始点初始化 91 for( int j = 1; j <= n; j ++ )//读入平台信息 92 scanf("%d%d%d",&platForms[j].Lx,& platForms[j].Rx, & platForms[j].h); 93 sort(platForms,platForms+n+1);//对平台由高到低排序 94 printf("%d\n", MinTime(0,true));//MinTime()方法求下平台的最小时间 95 } 96 return 0; 97 }
