欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

动态规划---Help Jimmy

程序员文章站 2022-07-16 10:02:07
...

题目描述:

动态规划---Help Jimmy

场景中包括多个长度和高度各不相同的平台,地面是最低的平台,高度为零,长度无限,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、贪心思路:下降到距离差更大的板子,这咋一看没问题,但这只是当前状态最优解,而不是整体最优解(如下图,明显第一条路是最优解)
动态规划---Help Jimmy
3、采用下降一层回头看一层的策略,由下图距离
动态规划---Help Jimmy
从三层出发,到二层,回头看第三层,可以算出时间是二、三层高度差 + 三层左侧距离(设为 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;
}
相关标签: mooc 数据结构