题目是动归,状态是比较轻松能够分出来的。

总的来说就是每一个加油点是一个状态,比如i点就由之前i-1个点确定,从起点到i-1每个点都走到i点一次,求出最小的时间,保存在i点。

需要注意的起点的处理以及终点。题目思路挺清晰的,只要注意下细节,给dp入门做练习还是挺不错的。

#include <cstdio>
#include <iostream>
using namespace std;
main()
{ int n,i,p[107],j,l,c,t,vr,v1,v2,len;
  double dp[107],tmp;
  while(scanf("%d",&l)!=EOF)
  {
      scanf("%d %d %d %d %d %d",&n,&c,&t,&vr,&v1,&v2);
      for(i=1;i<=n;i++)
        scanf("%d",&p[i]);
      if(v2>vr){printf("What a pity rabbit!\n");continue;}
      p[n+1]=l;p[0]=0;dp[0]=0.0;
      for(i=1;i<=n+1;++i)
      {
         int mi=min(p[i],c);
         dp[i]=1.0*mi/v1+1.0*(p[i]-mi)/v2;
         for(j=i-1;j>0;j--) 
             {
              len=p[i]-p[j];
              if(len>=c)
                 tmp=1.0*c/v1+1.0*(len-c)/v2;
              else tmp=1.*len/v1;
              dp[i]=min(dp[i],dp[j]+tmp+t);
              } 
       }
      if(dp[n+1]<1.0*l/vr)printf("What a pity rabbit!\n");
      else printf("Good job,rabbit!\n");
  }
  return 0;
}

Logo

腾讯云面向开发者汇聚海量精品云计算使用和开发经验,营造开放的云计算技术生态圈。

更多推荐