杭电acm2059-龟兔赛跑 java

一看题就知道是动态规划，不过这要看下如何设置变化数组了

先分析这道题：兔子到达终点的时间时固定的，因此只需要考虑乌龟了，乌龟骑电车和骑自行车的时间，然后计算，因为中间有N个充电站，可以看做N个点（到起点的点），加上起点和终点则是N+2的位置，这时我们dp，判断到每个点的最小时间，结果也就是第N+2个点的最短时间

起点时间是0.这是必须的，然后往后面DP

到第i个，就让j从0循环到i-1，依次代表从j站一直开到i站，这样得到到达i站所需要

的最短时间。

最后比较到达第n+2站(终点)的时间与兔子所花的时间就可以了。

上代码：

import java.util.Scanner;

public class Main {

    static int L;

    static int N,C, T;

    static int VR,VT1,VT2;

    static int p[]= new int [102];

    static double dp[]=new double [105];

    static void dp(){

        double ans,min;

    for(int i=0;i<105;i++)

        dp[i]=-1;

    dp[0]=0;

    for(int i=1;i<N+2;i++){

        min = 100000;

        for(int j=0;j<i;j++){

            int len=p[i]-p[j];

            if(len>C){

            ans=1.0*C/VT1+(len-C+0.0)/VT2;      //如果电量不能达到j到i的距离

            }

            else{

                ans=1.0*len/VT1;　　　　　　　　　　

            }

            ans+=dp[j];

            if(j!=0)

                ans+=T;　　　　　　　　　　　　　　　//过充电站，加上充电时间　

            if(min>ans)

                min=ans;

        }

        dp[i]=min;

    }

}

        Main(){

    Scanner sc=new Scanner(System.in);

        while(sc.hasNext()){

            L=sc.nextInt();

            N=sc.nextInt();

            C=sc.nextInt();

            T=sc.nextInt();

            VR=sc.nextInt();

            VT1=sc.nextInt();

            VT2=sc.nextInt();

            for(int i=1;i<=N;i++){

                p[i]=sc.nextInt();

            }

            p[0]=0;

            p[N+1]=L;

            dp();

            if(1.0*L/VR<dp[N+1])

                System.out.println("Good job,rabbit!");

            else

                System.out.println("What a pity rabbit!");

        }    

            }

    public static void main(String[] args) {

        new Main();

    }

}

巴特西

杭电acm2059-龟兔赛跑 java

最新文章

热门文章