动态规划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
", MinTime(0,true));//MinTime()方法求下平台的最小时间 
95     }
96 return 0;
97 }