动态规划---Help Jimmy

港控/mmm° 2023-07-02 11:22 16阅读 0赞

# 题目描述： #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70]

场景中包括多个**长度和高度各不相同的平台**，地面是最低的平台，高度为零，长度无限，Jimmy老鼠在时刻 0 从高于所有平台的某处开始下落，它的下落速度始终为1米/秒，当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒，当Jimmy跑到平台的边缘时，开始继续下落，Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束，设计一个程序，计算Jimmy到底地面时的最早时间

# 输入 #

第一行是测试数据的组数 `t（0 <= t <= 20）`  
每组测试数据的第一行是四个整数 N，X，Y，MAX，用空格分隔  
N是平台的数目（不包括地面）  
X 和 Y 是Jimmy开始下落的位置的横竖坐标  
MAX是一次下落的最大高度  
接下来的N行每行描述一个平台，包括三个整数，X1\[ i \]，X2\[ i \] 和 H\[ i \]  
H\[ i \]表示平台的高度  
X1\[ i \] 和 X2\[ i \]表示平台左右端点的横坐标  
`1 <= N <= 1000，-20000 <= X，X1[i]， X2[i] <= 20000，0 < H[i] < Y <= 20000（i = 1..N）`  
补充：所有坐标的单位都是米，Jimmy的大小和平台的厚度均忽略不计，如果Jimmy恰好落在某个平台的边缘，被视为落在平台上，所有的平台均不重叠或相连，测试数据保证问题一定有解

# 输出 #

对输入的每组测试数据，输出一个整数，Jimmy到达地面时的最早时间

# Example #

Input
    1
    3 8 17 20
    0 10 8
    0 10 13
    4 14 3
    
    Output
    23

# 正确代码 #

#include <sstream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <iterator>
    #include <string>
    #include <queue>
    #include <stack>
    #include <map> 
    #include <set>
    
    #define _for(i,a,b) for(int i=a;i<b;i++)
    #define _unfor(i,a,b) for(int i=a;i>=b;i--)
    #define RI(a) scanf("%d",&a)
    #define mset(a,val,n) for(int i=0;i<n;i++)a[i]=val;
    #define mset2(a,val,n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=val;
    #define FI freopen("D:\\in.txt","r",stdin)
    #define FO freopen("D:\\out.txt","w",stdout)
    
    using namespace std;
    typedef long long LL;
    /*-------下面为主要代码-------*/
     
    const int N=1005;
    const int M=20005;
     
    struct Time  //定义结构体
    { 
        int x1,x2,h;
    }a[N];
     
    int dp[N+2][2]; // 0：表示第i的木板左边到底部的最短时间
                  // 1: 表示第i的木板右边到底部的最短时间
     
    int n,x,y,max_h;
     
    int cmp(Time c,Time b) //排序函数
    { 
        return c.h > b.h; //从大到小排列
    }
     
    void left(int i) //左
    { 
        //如果平台i下面有平台，且两者相距不超过MAX
        int k = i+1;
        while( k<n+1 && a[i].h-a[k].h<=max_h ) //n+1处是地面
        { 
            //确保平台k在平台i的左下方，且小鼠可以跳到上面
            if(a[i].x1 >= a[k].x1 && a[i].x1 <= a[k].x2)
            { 
                //核心
                dp[i][0] = a[i].h-a[k].h + min(dp[k][0] + a[i].x1-a[k].x1 , dp[k][1]+a[k].x2-a[i].x1);
                return; //千万不要忘记:易错点+难点
            }
            k++;
        }
     
        if(a[i].h-a[k].h>max_h) //因为第二个条件出的循环即：不能到达下一平台
            dp[i][0]=INT_MAX;
        else  //这里的else是最有灵魂的地方：成败都在这
            dp[i][0]=a[i].h; //因为它下面没木板，直接落地
    }
     
    void right(int i)//右
    { 
        //如果平台i下面有平台，且两者相距不超过MAX
        int k=i+1;
        while(k<n+1 && a[i].h-a[k].h<=max_h)
        { 
            //确保平台k在平台i的右下方，且小鼠可以跳到上面
            if(a[i].x2<=a[k].x2 && a[i].x2 >= a[k].x1)
            { 
                dp[i][1]=a[i].h-a[k].h+min(dp[k][0] + a[i].x2-a[k].x1  ,  dp[k][1] + a[k].x2-a[i].x2);
                return;
            }
            k++;
        }
        if(a[i].h-a[k].h > max_h)//不能到达下一平台
            dp[i][1]=INT_MAX;
        else
            dp[i][1]=a[i].h; //因为它下面没木板，直接落地
    }
     
    int main()
    { 
        int t,i;
        scanf("%d",&t);
        while(t--)
        { 
            scanf("%d%d%d%d",&n,&x,&y,&max_h);//木板个数、老鼠的初始坐标、最大跳跃高度
     
            //地面也当做一块木板
            a[0].x1=-20000;
            a[0].x2=20000;
            a[0].h=0;
            //老鼠初始位置也当做一块木板
            a[1].x1=x;
            a[1].x2=x;
            a[1].h=y;
     
            for(i=2;i<=n+1;i++) //输入数据
                scanf("%d%d%d",&a[i].x1,&a[i].x2,&a[i].h);
     
            sort(a,a+n+2,cmp);  // 排序：一定要把sort用好
            memset(dp,0,sizeof(dp)); //初始化
     
            //为什么i是从n开始的呢？毋庸置疑n+1处是小鼠最初的位置往左往右都是0
            for(i=n; i>=0 ;i--)
            { 
                left(i);//进行左：去bfs
                right(i);//进行右：去bfs
            }
            int time=min(dp[0][0],dp[0][1]); //取最小值
            printf("%d\n",time); //输出结果
        }
        return 0;
    }

--------------------

### 下面是我自己写了半天还没通过的代码，别参考了，别看了 ###

# 解析 #

##### 代码的简洁程度取决于对题目的理解程度，下面我说一些对本题的理解 #####

**1、场景中包括多个长度和高度各不相同的板子（平台）**，说明所有板子都是上下参差不齐的，写代码时不用考虑同一平面优先到哪一块板子，只用考虑不同高度优先下降到哪一块板子

2、**贪心思路：下降到距离差更大的板子**，这咋一看没问题，但这只是当前状态最优解，而不是整体最优解（如下图，明显第一条路是最优解）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 1]  
3、**采用下降一层回头看一层的策略**，由下图距离  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 2]  
从三层出发，到二层，回头看第三层，可以算出时间是二、三层高度差 + 三层左侧距离（设为 t1），再到一层，回头看第二层和第三层，第一种时间是 t1 + 二层右侧距离 + 一二层高度差，第二种时间是一层右侧距离+一三层高度差，最后取最小就得出到达第一层所用时间的最优解

那么我们可以类比一下，若有很多层，每一层的时间就为 **t + 回头看的层数左或右侧距离 + 回头看的层数与本层数高度差**，而 t 即回头看的那层到最顶层所用的最优时间，再取最小值，因此这样就可以得出到达最底层所用时间的最优解

# 代码（别参考，没通过） #

#include <sstream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <iterator>
    #include <string>
    #include <queue>
    #include <stack>
    #include <map> 
    #include <set>
    
    #define _for(i,a,b) for(int i=a;i<b;i++)
    #define _unfor(i,a,b) for(int i=a;i>=b;i--)
    #define RI(a) scanf("%d",&a)
    #define mset(a,val,n) for(int i=0;i<n;i++)a[i]=val;
    #define mset2(a,val,n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=val;
    #define FI freopen("D:\\in.txt","r",stdin)
    #define FO freopen("D:\\out.txt","w",stdout)
    
    using namespace std;
    typedef long long LL;
    /*-------下面为主要代码-------*/
    
    const int N=1005; //最大层数 
    const int M=20005; //绝对值最大坐标 
    
    struct Time
    { 
        int x1,x2,h; //x1是左侧坐标,x2是右侧坐标,h是本层高度 
    }a[N]; //N层板子 
     
    int dp[N]; //代表当前当前层到最顶层的最短时间 
     
    int n,x,y,max_h;
     
    int cmp(Time c,Time b) //排序函数
    { 
        return c.h > b.h; //从大到小排列
    }
     
    void back(int i)
    { 
        int k = i+1;
        int tmp1,tmp2;
        while( k<=n+1 && a[k].h-a[i].h<=max_h ) //回头看上一层 
        { 
            if(a[k].x1 >= a[i].x1 && a[k].x1 <= a[i].x2) 
            { 
                //上一层左侧到这一层左侧的最短时间
                tmp1 = dp[k] + (a[k].x1 - a[i].x1) + (a[i].h - a[k].h);
            }
            if(a[k].x2 >= a[i].x1 && a[k].x2 <= a[i].x2)
            { 
                //上一层右侧到这一层右侧的最短时间
                tmp2 = dp[k] + (a[i].x2 - a[k].x1) + (a[i].h - a[k].h);
            }
            if(i==0)
            { 
            	tmp1-=a[k].x1 - a[i].x1;
            	tmp2-=a[i].x2 - a[k].x1;
    		}
            dp[i] = max(tmp1,tmp2);
            k++; //再回头看上一层
        }
    }
     
    int main()
    { 
        int t; //t代表测试组数 
        scanf("%d",&t);
        while(t--)
        { 
            scanf("%d%d%d%d",&n,&x,&y,&max_h);//木板个数、老鼠的初始坐标、最大跳跃高度
     
            //地面也当做一块木板
            a[0].x1=-20000;
            a[0].x2=20000;
            a[0].h=0;
            //老鼠初始位置也当做一块木板
            a[n+1].x1=x;
            a[n+1].x2=x;
            a[n+1].h=y;
     
            for(int i=1;i<=n;i++)
                scanf("%d%d%d",&a[i].x1,&a[i].x2,&a[i].h);
     
            sort(a,a+n+1,cmp);
            mset(dp,0,sizeof(dp));
     
    		for(int i=n; i>=0 ;i--)
            { 
                back(i);
            }
            printf("%d\n",dp[0]);
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200129140711244.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200129143439399.JPG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200129144025328.JPG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70