1262 - Atomic Car Race

AOJ

問題

車のレースをする。
１台の車だけを考える。
n個のチェックポイントでタイヤを交換するかしないか選ぶことができる。
ここで、n個目のチェックポイントがゴールである。
タイヤを交換した場所からの距離をxとすると、xからx+1まで走るのにかかる時間は、


1/(v - e × (x - r)) (if x > r)
1/(v - f × (r - x)) (if x < r)


となる。v,e,f,rは与えられる一定の値。
このとき、ゴールするのにかかる最短時間を求めよ。

解法

距離は全て整数になるので、距離x進むのにかかる時間をテーブルとして計算しておく。
DP[i] = i番目のチェックポイントに行く最短時間
それぞれのチェックポイントに対して、先にあるチェックポイント全てに配るDPをすればいい。

ソース

int main() {
  int n;
  while(cin>>n,n) {
    int a[n+1];
    a[0] = 0;
    REP(i,n) cin >> a[i+1];
    double b,r,v,e,f;
    cin>>b>>r>>v>>e>>f;
    double timetable[10001];
    timetable[0] = 0;
    REP(x,10001) {
      double t;
      if (x>=r) t = 1/(v-e*(x-r));
      else t = 1/(v-f*(r-x));
      timetable[x+1] = timetable[x] + t;
    }
    vector<double> dp(n+1,INF);
    dp[0]=0;
    
    REP(i,n) {
      for (int j=i+1; j<n+1; ++j) {
        double t = timetable[a[j]-a[i]];
        if (i) t += b;
        dp[j] = min(dp[j], dp[i] + t);
      }
    }
    printf("%.12f\n",dp[n]);
  }
}