hdu 2059 龟兔赛跑（DP） - c++编程基础

题目没有说明白的是，不能用电动车剩余的能力，每次都要充满。

题目分析：

动态规划问题，可以对站点进行DP，加上起点和终点一共有n+2个站，起点表示站点0，dp[n+1]就是乌龟的最优时间，即最短时间，那么动态转化方程为：dp[i]=min(dp[i],dp[j]+t1); t1:从j到i的最优（最少）时间。

AC代码：

/**
  *@xiaoran
  *DP,题意不清楚，不能用上次剩下的能量
  *dp[i]=min(dp[i],dp[j]+cost),cost:从j——>i的时间
  */
#include
  
   
#include
   
     #include
     #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #define LL long long using namespace std; const double DOB_MAX=1000000.0; int path[110]; double dp[110]; int main() { int l,n,c,t,vr,vt1,vt2; while(scanf(%d,&l)==1){ scanf(%d%d%d,&n,&c,&t); scanf(%d%d%d,&vr,&vt1,&vt2); for(int i=1;i<=n;i++){ scanf(%d,&path[i]); } path[n+1]=l; dp[0]=0; double t1,t2; for(int i=1;i<=n+1;i++){ dp[i]=DOB_MAX; for(int j=0;j
              
               =len) t1=len*1.0/vt1;//全程电动车 else t1=c*1.0/vt1+(len-c)*1.0/vt2;//用电动车走c，剩下的脚蹬 if(j) t1+=t;//算上加油的时间 //2、不加油 t2=len*1.0/vt2; t1=min(t1,t2);//从i到j的最小花费 dp[i]=min(dp[i],dp[j]+t1); } } if(dp[n+1]
               
                ?