Posted on 2010-11-19 13:34
小小菜鸟蛋 阅读(639)
评论(0) 编辑 收藏 引用 所属分类:
某蛋的解题报告
http://acm.hdu.edu.cn/showproblem.php?pid=2059dp[i]表示乌龟到达第i个充电站时最少花费时间
到第 i 个充电站后，从起点开始遍历到第 i-1 个充电站，得到最少花费时间
dp[i] = min(dp[j] + time(j-->i) ) + t
ì len / vt1, len <= c
time(j-->i) =
í î c / vt1 + (len-c) / vt2, len > c
(len = p[i] - p[j])
01 #include <cstdio>
02 #include <cstring>
03 using namespace std;
04
05 const int N = 110;
06 int p[N];
07 double dp[N];
08
09 int main()
10 {
11 int L, n, c, t, vr, vt1, vt2;
12 while (scanf("%d", &L) != EOF)
13 {
14 memset(dp, 0, sizeof(dp));
15 scanf("%d%d%d%d%d%d", &n, &c, &t, &vr, &vt1, &vt2);
16 for (int i = 1; i <= n; i++)
17 scanf("%d", &p[i]);
18 p[n+1] = L;
19 for (int i = 1; i <= n + 1; i++)
20 {
21 double min = 99999999999.0;
22 for (int j = 0; j < i; j++)
23 {
24 int len = p[i] - p[j];
25 double time = dp[j] + (len > c ? (c*1.0/vt1 + (len-c)*1.0/vt2) : (len*1.0/vt1));
26 if (j) //起点不用等待充电
27 time += t;
28 min = time < min ? time : min;
29 }
30 dp[i] = min;
31 }
32 if (dp[n+1] < L*1.0/vr)
33 printf("What a pity rabbit!\n");
34 else
35 printf("Good job,rabbit!\n");
36 }
37 }