首页 > 其他 > 详细

HDU2059

时间:2015-03-10 17:05:54      阅读:407      评论:0      收藏:0      [点我收藏+]

dp,题意自己看,不再赘述
把起点和终点和起点也看做加油站,则用dp数组来记录到每个加油站的最短时间
dp[i]=min(dp[j]+t,dp[i]) 0<=j<i
即到达第i个加油站的最短时间是由前i个加油站直接到第i个加油站中最短的时间,t表示从第j个加油站途中不加油到第i个加油站的时间

#include <iostream>
#define INF 999999
using namespace std;
double dp[105];
int main()
{
    int L;
    int dis[105];
    while(cin>>L)
    {
        int n,c,t;
        cin>>n>>c>>t;
        int vr,vt1,vt2;
        cin>>vr>>vt1>>vt2;
        for(int i=1;i<=n;i++)
            cin>>dis[i];
        dis[0]=0;
        dis[n+1]=L;
        double tem;
        for(int i=1;i<105;i++)//初始化要到位!!由于<100WA了两发
            dp[i]=INF;
        dp[0]=0;
        for(int i=1;i<=n+1;i++)
        {
            for(int j=0;j<i;j++)
            {
                int len=dis[i]-dis[j];
                if(len<=c)
                    tem=len*1.0/vt1;
                else
                    tem=(len-c)*1.0/vt2+c*1.0/vt1;
                if(j!=0)
                    tem+=t;
                dp[i]=min(dp[j]+tem,dp[i]);
            }
        }
        double tt=L*1.0/vr;
        if(dp[n+1]>tt)
            printf("Good job,rabbit!\n");
        else
            printf("What a pity rabbit!\n");
    }
    return 0;
}

 

HDU2059

原文:http://www.cnblogs.com/wzsblogs/p/4326264.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!