1262:Atomic Car Race

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1262

無限にエネルギーのある車でレースをする。距離0の地点からスタートし、途中n個のチェックポイントがある。チェックポイントではタイヤの交換ができる。タイヤの交換にはb秒かかる。タイヤを交換すると走る時間が変わる。n個目のチェックポイントまで行くときの最小の時間を求めよ。

まず、0~10000までの全ての距離を走る時間を与えられた式によって計算しておく。
そして、
dp[ チェックポイント ]:=最短時間
とすると、DAGになっているので最短経路のようにしてdpで簡単に求められる。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#define INF 1<<29
#define all(c) (c).begin(),(c).end()

using namespace std;

int main(void){

  int n;
  while(cin >> n,n){
    vector<int>a(n+1);
    a[0]=0;
    for(int i=1;i<=n;i++)cin >> a[i];
    double b,r,v,e,f;
    cin >> b >> r >> v >> e >> f;

    double time[10001];
    time[0]=0;
    for(int i=0;i<10001;i++){
      if(i>=r)time[i+1]=1/(v-e*(i-r))+time[i];
      else time[i+1]=1/(v-f*(r-i))+time[i];
    }
    double dp[101];
    fill(dp,dp+101,INF);
    dp[0]=0;
    for(int i=0;i<n;i++)
      for(int j=i+1;j<=n;j++)
	dp[j]=min(dp[j],dp[i]+time[a[j]-a[i]]+(i>0)*b);

    printf("%.4f",dp[n]);
    cout << endl;
  }
  return 0;
}