龟兔赛跑 HDU - 2059

点击查看题目

难点和思路：

难点是要考虑路程中是否在每一个充电桩充电，如何不漏下所有可能的状态。思路是计算乌龟到终点的最短时间。

让表示到达第个充电站的最优解，起点用表示,终点用表示，再枚举前面的充电站直接到所花的时间，就能覆盖到全部情况。

关于为什么dp是1维：最优解只与停下的充电桩有关。

例如：

在2，3号充电站都不需要充电，那么(j=1)~(i=4)这次枚举就包括了这个情况。

在3号充电站不需要充电，那么(j=2)~(i=4)这次枚举就包括了这个情况。

在3号充电站需要充电，那么（j=3）~(i=4)这次枚举就包括了这个情况。

注意：0号充电站（起点）充电不耗时，开始位置时间为0。

#include<cstdio>
#include<cstring>
#include<algorithm>

double dp[1001];
double p[1001];

int main(){
    int L;
    while(scanf("%d",&L)==1&&L){
        int n;
        double Vr,v1,v2,c,T;scanf("%d%lf%lf%lf%lf%lf",&n,&c,&T,&Vr,&v1,&v2);
        for(int i=1;i<=n;++i)scanf("%lf",&p[i]);p[0]=0,p[n+1]=L;
        std::fill(dp,dp+1001,99999999);dp[0]=0;

        for(int i=1;i<=n+1;++i){
            for(int j=0;j<i;++j){
                if(p[i]-p[j]<c){
                    dp[i]=std::min(dp[i],dp[j]+(p[i]-p[j])/v1+ (j==0?0:T));
                }
                else{
                    dp[i]=std::min(dp[i],dp[j]+c/v1+(p[i]-p[j]-c)/v2+ (j==0?0:T));
                }
            }
        }
        if(dp[n+1]>(double)L/Vr)printf("Good job,rabbit!\n");
        else printf("What a pity rabbit!\n");

    }
    return 0;
}