HDU2059 龟兔赛跑（多决策的动态规划）

题目链接：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;
}