这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2059
看了网上有人写了思路,直接COPY过来了:
一维数组的动态规划 |
与第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;
}