hdu 2059(dp)

时间:2022-07-25 18:13:55

题意:容易理解...

思路:dp[i]表示乌龟到达第i个充电站时最少花费时间到第 i 个充电站后,从起点开始遍历到第 i-1 个充电站,得到最少花费时间

状态转移方程:dp[i]=min(dp[j]+time(j-->i));  1<=j<=i-1

代码实现:

#include<stdio.h>
#include<string.h>
int main()
{
int i,j,n;
double l,c,t,vr,v1,v2,temp,len,min;
double a[],dp[];
while(scanf("%lf",&l)!=EOF)
{
scanf("%d%lf%lf",&n,&c,&t);
scanf("%lf%lf%lf",&vr,&v1,&v2);
for(i=;i<=n;i++)
scanf("%lf",&a[i]);
a[n+]=l;a[]=;dp[]=;
for(i=;i<=n+;i++)
{
min=;
for(j=i-;j>=;j--)
{
len=a[i]-a[j];
if(len>c)
temp=c/v1+(len-c)/v2;
else
temp=len/v1;
if(j)
temp=temp+t;
if(min>temp+dp[j])
min=temp+dp[j];
}
dp[i]=min;
}
if(dp[n+]>l/vr)
printf("Good job,rabbit!\n");
else
printf("What a pity rabbit!\n");
}
return ;
}