https://atcoder.jp/contests/gigacode-2019/submissions/13239335
これでdif12Kなのか。天才しかいない。
- 初期値は all(dp)=ldbl_max, dp[0]=0
- 繰り返しは rep(i, 1, N+2) rep(j, 0, i)
- 更新は dp[i] = min(dp[i], dp[j] + (ld)(car[i].x - car[j].x) / (ld)car[j].v);
- 出力は dp[N+2]
制約からDPっぽいという事までは凡人でも感じるとは思う。問題はDPの定義。DP[i]を車[i]の終点に着目して定義しようとすると実装が難しい。今回はX[i]から車が出発することからDP[i]をX[i]までの最善とする。X[i]でソートし、更新式は以下のようになる。
ゴール地点に架空の車を追加するとコーディングしやすい。スタート地点の車とゴール地点の車も考慮してdp[N+2]の値が求める答えとなる。計算量はだが、制約から処理できる。
