hdu2059 参考答案

   1 /*
   2 DP
   3 hdu2059 龟兔赛跑
   4 ymc 2008/9/23
   5 题目大意：
   6 乌龟与兔子赛跑，起点为0，终点为len。
   7 兔子以恒定的速度vr跑。乌龟骑着电动车。
   8 电动车的速度为vt1，满电能跑c的距离，一次充电需要t的时间。
   9 起始状态电动车满电，路上有n个充电点，分别距离起点p1,p2,..,pn。
  10 求兔子在比赛中能否获胜。
  11 分析与解题思路：
  12 重点在于求解乌龟到终点的最短时间。
  13 把起点和终点作为两个充电点。
  14 令Time[i]为乌龟到代第i个充电点的最短时间。
  15 Cap[i]为乌龟最早到代第i个充电点时电动车的最大余量。
  16 Time[0]=0;Cap[0]=c;
  17 则Time[i]=Min{Time[j]+Go(j,i)},0<=j<i;
  18 其中Go(j,i)表示从j个充电点直接到i个充电点的最短时间，
  19 如果有多个解，要求电动车余量最大。
  20 
  21 */
  22 #include <iostream>
  23 #include <limits>
  24 using namespace std;
  25 const int N=110;
  26 double p[N];
  27 int n;
  28 double len,c,t;
  29 double vr,vt1,vt2;
  30 double Time[N];
  31 double Cap[N];
  32 void Init()//把起点和终点看作充电点
  33 {
  34     scanf("%d %lf %lf",&n,&c,&t);
  35     scanf("%lf %lf %lf",&vr,&vt1,&vt2);
  36     p[0]=0;
  37     for(int i=1;i<=n;i++)
  38         scanf("%lf",&p[i]);
  39     n++;
  40     p[n]=len;
  41     n++;
  42 }
  43 /*
  44 从第x个充电点直接到第y个充电点，到第y个充电点时的最短时间。
  45 如果时间相同，电动车余量最大。
  46 */
  47 void Go(int x,int y,double &tt,double &tc)
  48 {
  49     double t1=Time[x];
  50     double t2=Time[x];
  51     double c1=Cap[x];
  52     double c2=Cap[x];
  53     double len=p[y]-p[x];
  54     //在第x个点不充电直接走
  55     if(len<=c1)
  56     {
  57         t1+=len/vt1;
  58         c1-=len;
  59     }
  60     else
  61     {
  62         t1+=c1/vt1;
  63         len-=c1;
  64         t1+=len/vt2;
  65         c1=0;
  66     }
  67 
  68     //在第x个点充电后再走。
  69     t2+=t;
  70     c2=c;
  71     len=p[y]-p[x];
  72     if(len<=c2)
  73     {
  74         t2+=len/vt1;
  75         c2-=len;
  76     }
  77     else
  78     {
  79         t2+=c2/vt1;
  80         len-=c2;
  81         c2=0;
  82         t2+=len/vt2;
  83     }
  84     if(t1<t2||t1==t2&&c1>c2)
  85     {
  86         tt=t1;
  87         tc=c1;
  88     }
  89     else
  90     {
  91         tt=t2;
  92         tc=c2;
  93     }
  94 }
  95 
  96 void DP()
  97 {
  98     memset(Time,0,sizeof(Time));
  99     memset(Cap,0,sizeof(Cap));
 100     Time[0]=0;
 101     Cap[0]=c;
 102     double Min,Maxc;
 103     double tt,tc;
 104     for(int i=1;i<n;i++)
 105     {
 106         Min=INT_MAX;
 107         Maxc=INT_MIN;
 108         for(int j=0;j<i;j++)
 109         {
 110             Go(j,i,tt,tc);
 111             if(tt<Min||tt==Min&&tc>Maxc)
 112             {
 113                 Min=tt;
 114                 Maxc=tc;
 115             }
 116         }
 117         Time[i]=Min;
 118         Cap[i]=Maxc;
 119     }
 120     double t1=len/vr;
 121     if(t1<Time[n-1])
 122         printf("Good job,rabbit!\n");
 123     else
 124         printf("What a pity rabbit!\n");
 125 }
 126 
 127 int main()
 128 {
 129     while(scanf("%lf",&len)!=EOF)
 130     {
 131         Init();
 132         DP();
 133     }
 134 }