hdu2059 龟兔赛跑 DP

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2059

虽然知道是DP ，刚开始一直没有想出状态转移方程。

刚开始的思路就是定义dp[i]表示到达第i个加油站的最优时间，但是却一直在想其与在第i-1的加油站加油和不加油之间的转移关系

后来看别人的思路，觉得自己又弱了，应该是考虑和前面的所有加油站的关系

对于每一个站点i, 我们可以假设在j (0<=j<i) 满电出发，那么：

如果i到j的距离小于c, 就可以从j一直骑到i

如果i到j的距离大于c, 要骑一段蹬一段

状态转移方程就很好写了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 using namespace std;
 6 double d[110];
 7 double dp[110];
 8 void init()
 9 {
10         memset(d,0,sizeof(d));
11         for(int i=0;i<110;i++)
12                 dp[i]=10001010;
13 
14 }
15 int main()
16 {
17      double l;
18      while(scanf("%lf",&l)!=EOF)
19      {
20            
21              init(); 
22              int n;
23              double c,t;
24              double vr,v1,v2;
25              cin>>n>>c>>t;
26              cin>>vr>>v1>>v2;
27              for(int i=1;i<=n;i++)
28                      scanf("%lf",&d[i]);
29                      d[0]=0;
30                      d[n+1]=l;
31              double s;
32              dp[0]=0;
33              for(int i=1;i<=n+1;i++)
34                      for(int j=0;j<i;j++)
35                              {
36                                      s=d[i]-d[j];
37                                      if(s<=c)
38                                      dp[i]=min(dp[i],dp[j]+s/v1+t);
39                                      else
40                                      dp[i]=min(dp[i],dp[j]+c/v1+(s-c)/v2+t);
41                              }
42             double t1=l/vr;
43             dp[n+1]=dp[n+1]-t;
44            if(t1>dp[n+1]) cout<<"What a pity rabbit!"<<endl;
45            else cout<<"Good job,rabbit!"<<endl;
46      }
47      return 0;
48 }

View Code

代码：