题目

龟兔赛跑

题解

参考博客：HDU 2059 龟兔赛跑（DP）

代码

#include<bits/stdc++.h>
using namespace std;
#define INF 100000000
const int N = 1110;
int main() {
	int l, n, c, t, vr, v1, v2, p[N]; 
	//dp[i]表示到第i个充电站所用最少的时间
    double t1, t2, dp[N], min;   
	while(cin >> l) {
        scanf("%d%d%d%d%d%d", &n, &c, &t, &vr, &v1, &v2);
        for(int i = 1; i <= n; i ++)
            cin >> p[i];  
        //将起点当做第0个充电站
        p[0] = 0;   
        //终点 
        p[n + 1] = l;
        //乌龟的时间 
        dp[0] = 0;
        for(int i = 1; i <= n + 1; i++) {
        	//花费的最少时间 
            min = INF;
            //从第0个充电桩开始遍历直前一个充电站 
            //只考虑 从j充电一路到i的情况
			//j不充电的情况 会包含在 之前充电桩充电一路到i的情况中 
            for(int j = 0; j < i; j++) {
            	//距离 
                int dis = p[i] - p[j];
                if(dis > c)
                    t2 = (double)c / v1 + (double)(dis - c) / v2;
                else
                    t2 = (double)dis / v1;
                t2 += dp[j];
                //充电
                if(j)   
                    t2 += t;
                //找最小的时间
                if(min > t2)   
                    min = t2;
            }
            dp[i] = min;
        }
        //兔子用的时间
        t1 = (double)l / vr; 
		  
        if(t1 > dp[n + 1])
        	printf("What a pity rabbit!\n");
        else
            printf("Good job,rabbit!\n");
	}
	return 0;
}