递归，动态规划，找最短路径，Help Jimmy-白红宇

递归，动态规划，找最短路径，Help Jimmy

阅读量：6435 次

发布时间：2019-06-23

本文共 1261 字，大约阅读时间需要 4 分钟。

题目链接：

解题报告：

1、老鼠每次来到一块木板上都只有两条路可以走，可以使用递归

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define _MAX 1010#define INF 0x3f3f3f3fstruct Platform{    int lx;//木板左端的坐标    int rx;//木板右端的坐标    int h;//木板距离地面的高度} p[_MAX];int MAX,n;int leftmin[_MAX];//从每条木板左端到地面的最短时间int rightmin[_MAX];int My_Compare(const void *e1,const void *e2)//快速排序中用到，较高的木板放在前面{    struct Platform *p1,*p2;    p1=(struct Platform*)e1;    p2=(struct Platform*)e2;    return p2->h-p1->h;}int mintime(int L,int flag)//从编号为L的木板上跳下，flag 表示将要从木板跳下的方向，flag=1时为左边跳下{    int y=p[L].h;    int i,x,ltime,rtime;    if(flag)        x=p[L].lx;//x为jimmy的坐标，表示来到了木板的左端    else x=p[L].rx;    for(i=L+1; i<=n; i++) //开始找木板    {        if(p[i].lx<=x&&p[i].rx>=x)            break;    }    if(i<=n)//找到木板但是会摔死    {        if(y-p[i].h>MAX)            return INF;    }    else//下面没有木块了    {        if(y>MAX)            return INF;        else return y;//没有木板直接跳下来    }    ltime=y-p[i].h+x-p[i].lx;    rtime=y-p[i].h+p[i].rx-x;    if(leftmin[i]==-1)        leftmin[i]=mintime(i,1);    if(rightmin[i]==-1)        rightmin[i]=mintime(i,0);    ltime+=leftmin[i];    rtime+=rightmin[i];    if(ltime