SRM543 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=11912&rd=14735

DP[どの島][どの港]
普通にループを回すと当然のがら間に合わない。

何分探索かして今注目している位置より左から適切な場所を探すのかと思ったけど、そんなことはなかった。
最小値あたりのインデックスを持っておいて、距離の近い方へと見ていく。

double f(double x, double y)
{
  return sqrt(x * x + y * y);
}

class EllysRivers {
public:
  double getMin(int length, int walk_, vector <int> width_, vector <int> speed_)
  {
    vector<double> width(width_.begin(), width_.end());
    vector<double> speed(speed_.begin(), speed_.end());
    double walk = walk_;

    const int N = width.size();
    const int M = 50 + 5;
    const int L = 100000 + 5;

    static double dp[M][L];
    fill(&dp[0][0], &dp[M - 1][L - 1] + 1, 1e128);
    for (int i = 0; i < L; ++i) {
      dp[0][i] = i;
      dp[0][i] /= walk;
    }
    for (int i = 1; i <= N; ++i) {
      dp[i][0] = dp[i - 1][0] + width[i - 1] / speed[i - 1];
    }

    for (int i = 1; i <= N; ++i) {
      for (int j = 1, k = 0; j <= length; ) {
        double b = dp[i - 1][k + 0] + f(j - (k + 0), width[i - 1]) / speed[i - 1];
        double c = dp[i - 1][k + 1] + f(j - (k + 1), width[i - 1]) / speed[i - 1];
        if (b <= c) dp[i][j++] = min(b, c);
        else ++k;
      }
      for (int j = 1; j <= length; ++j) {
        dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1.0 / walk);
      }
    }

    return dp[N][length];
  }