HDU(2059)動態規劃問題

對於動態規劃問題，可以按步驟來做：

1、分解出子問題。

2、求得子問題的最優解。

首先將問題轉化為：到達一個站點 i 的最優解 。

對於每一個站點 i ，我們可以假設在第 j ( 0 < j < i ) 個站點充滿電出發，一共有兩種狀態：

(1) 當從第j個站點到第i個的距離大於電動車能夠行使的距離時，需要開與騎相結合。

(2) 當從第j個站點到第i個的距離小於電動車能夠行使的距離時 ，只需要開到。

#include
#include
#include
using namespace std ;
int main()  {
    int s ;
    while(cin >> s) {
        int count , can , t ;
        int path[110] ;
        double dp[110] ;
        cin >> count >> can >> t ;
        path[0] = 0 ;
        path[count + 1] = s ;
        dp[0] = 0.0 ;
        int v1 , v2 , v3 ;
        cin >> v1 >> v2 >> v3 ;
        for(int i = 1 ; i <= count  ; i++)
            cin >> path[i] ;
        for( int j = 1 ; j <= count + 1 ; j++ ) {
            dp[j]=100000.0 ;
            for( int k = 0 ; k < j ; k++ )  {
                 double len = ( path[j] - path[k] ) * 1.0 ;
                 double temp = ( len > can ? (can * 1.0 / v2 + (len - can) * 1.0 / v3 ) : ( len * 1.0 / v2 )  ) ;
                 if(k)
                    temp += t ;
                 dp[j] = min(dp[j] , dp[k]+temp) ;
            }
        }
        double tt = s * 1.0 / v1 ;
        if( dp[count+1] < tt )
            puts("What a pity rabbit!");
        else
            puts("Good job,rabbit!");
    }
    return 0 ;
}