hdu 2059 龜兔賽跑(DP)
題目沒有說明白的是,不能用電動車剩余的能力,每次都要充滿。
題目分析:
動態規劃問題,可以對站點進行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