HDOJ 2059 龟兔赛跑


题目地址:

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


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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Author: Tanky Woo
// HDOJ 2059
#include <iostream>
#include <string>
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; j<i; ++j)
	  		 {
	  		     int len = dis[i]-dis[j];
	  		     tmp =len>cLen? (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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 2059 龟兔赛跑》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注