hdu 2059 簡單動態規劃

該題目需要從整體考慮，對於充電站和終點這N+1個點，到達他們的最短時間肯定是從他們前邊的某個點沖完電後直接到達的。用t[i]記錄到第i個點時的最短距離，則t[i]就是從0——>(i-1)這些點沖滿電直接到點i所用時間的最小值。 [cpp]   #include<stdio.h>   int L,N,C,T,Vr,Vt1,Vt2,q[111];   double t[111];      void time()   {    int i,j;    double min,tim;    for(i=1;i<=N+1;i++)    {     if(C>=q[i])      min=1.0*q[i]/Vt1;     else      min=1.0*C/Vt1+1.0*(q[i]-C)/Vt2;     for(j=1;j<i;j++)     {      if(C>=q[i]-q[j])       tim=1.0*(q[i]-q[j])/Vt1+1.0*t[j]+1.0*T;      else       tim=1.0*C/Vt1+1.0*(q[i]-q[j]-C)/Vt2+1.0*t[j]+1.0*T;      if(tim<min)       min=tim;     }     t[i]=min;    }   }      int main()   {    int k;    double Tr,Tt;    while(scanf("%d",&L)!=EOF)    {     scanf("%d%d%d%d%d%d",&N,&C,&T,&Vr,&Vt1,&Vt2);     for(k=1;k<=N;k++)     {      scanf("%d",&q[k]);     }     q[N+1]=L;     time();     Tr=1.0*L/Vr;     Tt=t[N+1];     if(Tr<Tt)      printf("Good job,rabbit!\n");     else      printf("What a pity rabbit!\n");    }    return 0;   }