动态规划3--Help Jimmy

末蓝、 2022-01-06 23:25 181阅读 0赞

# 动态规划3--Help Jimmy #

## 一、心得 ##

## 二、题目 ##

![1163900-20170608061143512-1876725936.png][]

![1163900-20170608070727059-327292914.png][]

![1163900-20170608070525700-1096401620.png][]

![1163900-20170608070553247-1964227819.png][]

## 三、分析 ##

![1163900-20170608071102559-1763514799.png][]

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 }

![1163900-20170608070832153-1321723374.png][]

转载于:https://www.cnblogs.com/Renyi-Fan/p/6960829.html

[1163900-20170608061143512-1876725936.png]: /images/20211227/fa7f243d6cfe4dbeb5e8e73b8c00e572.png
[1163900-20170608070727059-327292914.png]: /images/20211227/6f9afdd426864c028ef096a6d52657a4.png
[1163900-20170608070525700-1096401620.png]: /images/20211227/65f08b96633f4fa9afef172fec97e931.png
[1163900-20170608070553247-1964227819.png]: /images/20211227/1d837c7eaf1a45df8d73dbffd2ea0a74.png
[1163900-20170608071102559-1763514799.png]: /images/20211227/44c167ead7fd4c4ab41b2fc6a2f5eab1.png
[1163900-20170608070832153-1321723374.png]: /images/20211227/d4de25d3924947a5827efbf41cf8fd0d.png