动态规划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 else15 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 24 #include 25 #include 26 #include 27 using namespace std;28 #define MAX_N 100029 #define INFINITE 100000030 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 else52 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 )// 跳到这块平台的高度如果大于Max60 return INFINITE;//返回无限大 61 }62 else { // 板子k左端正下方没有别的板63 if( y > maxHeight )//板子k的高度 h(k) 大于Max64 return INFINITE;//返回无限大 65 else66 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 } 