HDu 2059単純ダイナミックプランニング
1329 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=2059
この問題は全体的に考慮する必要があり、充電ステーションと終点のN+1点について、彼らに到着する最短時間は彼らの前のある点から電気を流してから直接到着したに違いない.t[i]でi番目の点までの最短距離を記録すると、t[i]は0-->(i-1)これらの点から点iに直接電力を供給するのにかかる時間の最小値である.
この問題は全体的に考慮する必要があり、充電ステーションと終点のN+1点について、彼らに到着する最短時間は彼らの前のある点から電気を流してから直接到着したに違いない.t[i]でi番目の点までの最短距離を記録すると、t[i]は0-->(i-1)これらの点から点iに直接電力を供給するのにかかる時間の最小値である.
#include<stdio.h>
int L,N,C,T,Vr,Vt1,Vt2,q[111];
double t[111];
void time()
{
int i,j;
double min,tim;
for(i=1;i<=N+1;i++)
{
if(C>=q[i])
min=1.0*q[i]/Vt1;
else
min=1.0*C/Vt1+1.0*(q[i]-C)/Vt2;
for(j=1;j<i;j++)
{
if(C>=q[i]-q[j])
tim=1.0*(q[i]-q[j])/Vt1+1.0*t[j]+1.0*T;
else
tim=1.0*C/Vt1+1.0*(q[i]-q[j]-C)/Vt2+1.0*t[j]+1.0*T;
if(tim<min)
min=tim;
}
t[i]=min;
}
}
int main()
{
int k;
double Tr,Tt;
while(scanf("%d",&L)!=EOF)
{
scanf("%d%d%d%d%d%d",&N,&C,&T,&Vr,&Vt1,&Vt2);
for(k=1;k<=N;k++)
{
scanf("%d",&q[k]);
}
q[N+1]=L;
time();
Tr=1.0*L/Vr;
Tt=t[N+1];
if(Tr<Tt)
printf("Good job,rabbit!
");
else
printf("What a pity rabbit!
");
}
return 0;
}