程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 2059 龜兔賽跑(DP)

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]

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved