龟兔赛跑(动态规划)

http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?cid=10541&pid=1006&ojid=0

本题和数塔差不多 找出所有到当前位置的方案,然后取用时最短的
如图

include<stdio.h>

include

using namespace std;
const int inf=0x3f3f3f3f;
int main()
{
int N;
double L,C,T,VR,VT1,VT2;
while(~scanf("%lf%d%lf%lf%lf%lf%lf",&L,&N,&C,&T,&VR,&VT1,&VT2))
{
double a[105];
double dp[105]= {0};
for(int i=1; i<=N; i++)
scanf("%lf",&a[i]);
a[0]=0;
a[N+1]=L;
for(int i=1; i<=N+1; i++)//到达终点时的最短距离所以是N+1
{
double min2=inf,t;
for(int j=0; j<i; j++)//所有到达i位置的方案
{
double jToi_L=a[i]-a[j];
if(jToi_L>C)//距离大于C肯定要步行的
t=C/VT1+(jToi_L-C)/VT2;
else t=jToi_L/VT1;
if(j!=0)//充电所需的时间
t+=T;
min2=min(min2,t+dp[j]);t+dp[j]=从j到达i位置最少的时间+从原点到达j位置的最短时间
}
dp[i]=min2;
}
if(dp[N+1]>(L/VR))
printf("Good job,rabbit! ");
else printf("What a pity rabbit! ");
}
return 0;
}
注意数据类型 (错了两次)

梦里不知身是客,一晌贪欢。
原文地址:https://www.cnblogs.com/dccmmtop/p/5443448.html