题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2059
分析：
兔子跑完全部路程的时间是定值，主要看乌龟如何走完全程，且用时最短。用这个最短的时间和兔子的时间相比。
首先我们可以把起点和终点都当作充电站，这样一共就有n+2个充电站，特殊情况是起点的充电站给车子充满电是不需要时间的，所以这个情况需要特判一下就是dp[0] = 0. 我们最终的目标是到达终点处的充电站所需要的时间最短。
接下来我们来推到状态转移方程，假设当前充电站是 i ，然后我们要枚举 0 - i-1个充电站，每个充电站选择充还是不充表达式为：dp[i] = min(dp[i], dp[j]+x, dp[j]+y]) x表示在第j个充电站充完电然后开到 i 所用的时间（中途不再充电） y表示在第j个充电站不充电，直接开到 i 所用的时间
PS：当然这里dp[j]+y实际不必要考虑，因为你在j-1号充电站判断是不是要充电的时候已经把在J号充电站不充电的情况考虑进去了。所以加不加问题不大，思路都是正确的。加了更容易理解，如果你熟练了以后可以直接去掉。
code:
#include <cstdio> #include <cmath> #include <algorithm> #include <cstring> using namespace std; const int INF = 0x3f3f3f3f; double dp[100+7]; int dis[100+7]; // 每个充电站到起点的距离 int main() { int l; while(scanf("%d", &l) != EOF) { int n, c, t; // 充电站的个数，充完电行驶的距离，充电所需时间 int vr, vt1, vt2; // 兔子的速度，骑车速度，脚蹬速度 scanf("%d %d %d", &n, &c, &t); scanf("%d %d %d", &vr, &vt1, &vt2); dis[0] = 0; dis[n+1] = l; for(int i=1; i<=n; i++) scanf("%d", &dis[i]); // memset(dp, 0x3f, sizeof(dp)); double类型不能用memset dp[0] = 0; for(int i=1; i<107; i++) dp[i] = INF; double tmp; for(int i=1; i<=n+1; i++) // 先枚举1到n+1个充电站 { for(int j=0; j<i; j++) // 枚举当前充电站之前的充电站 { int len = dis[i] - dis[j]; // 两个充电站之间的距离 if(len <= c) tmp = 1.0 * len / vt1; else tmp = 1.0 * c/vt1 + 1.0 * (len-c) / vt2; if(j != 0) // 因为考虑从的是在j充电站充电所以要加上充电的时间 tmp += t; dp[i] = min(dp[j]+tmp, dp[i]); } } double tr = 1.0 * l /vr; // 兔子所用时间 if(dp[n+1] > tr) printf("Good job,rabbit!\n"); else printf("What a pity rabbit!\n"); } return 0; }
