hdu_2059 龟兔赛跑

Posted on 2010-11-19 13:34 小小菜鸟蛋 阅读(658) 评论(0)  编辑 收藏 引用 所属分类: 某蛋的解题报告
http://acm.hdu.edu.cn/showproblem.php?pid=2059

dp[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 }

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理