Tanky WooRSS

HDOJ 2059 龟兔赛跑

06 Aug 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=2059


看了网上有人写了思路,直接COPY过来了:

Problem Analyse

 

一维数组的动态规划

Algorithm Analyse

 

与第2037题一样的算法。 我们把起点和终点,以及中间的n个充电站看做n+2个点。 这里长度为n+2的数组里保存的到达该站点所需时间的最优解。 自然,D0的值就是0。 然后依次往下规划。 到了第i点后,就让j从0循环到i-1,依次代表从j站充满了电一直开到i站,这样得到到达i站所需要的最短时间。 最后比较到达第n+2站(终点)的时间与兔子所花的时间就可以了。


DEV-CPP的缩进功能感觉不太好使。。。 等电脑回来了还是安VS。。。

// Author: Tanky Woo
// HDOJ 2059
#include 
#include 
using namespace std;

//  Accepted 2059 15MS 216K 1716B C++ Tanky Woo 
const int maxNum = 0xFFFF;
int nLength;  // 跑道长度 
int nNum, cLen, tTime; // 分别表示 充电站个数, 其中每个数都在32位整型范围之内。

int vr, vt1, vt2;
int dis[110];
double bstTime[110];   // 最优解 

int main()
{
    double tmp;
    while(scanf("%d", &nLength;) != EOF)
    {
         for(int i=0; i<110; ++i)
            bstTime[i] = 0.0;
         scanf("%d %d %d", &nNum;, &cLen;, &tTime;);
         scanf("%d %d %d", &vr;, &vt1;, &vt2;);
         for(int i=1; i<=nNum; ++i)
             scanf("%d", &dis;[i]);
         bstTime[0] = 0.0;
         dis[0] = 0;
         dis[nNum+1] = nLength;
         for(int i=1; i<=nNum+1; ++i)
         {
             double min = maxNum;
             for(int j=0; jcLen? (double)cLen/vt1+(double)(len-cLen)/vt2 : (double)len/vt1;
                 if(j)   // 当j==0时,表示在起点 
                    tmp += tTime;
                 tmp += bstTime[j];
                 if(tmp < min)
                    min = tmp;
              }
              bstTime[i] = min;
          }
          if(bstTime[nNum+1] <= (double)nLength/vr)
               printf("What a pity rabbit!\n");
          else
               printf("Good job,rabbit!\n");
      }
      return 0;
}