LeetCode Weekly Contest 282 復習

leetcode.com

Rank 4615 / 22307 4問目DPが解けなかった

問題

1. . Minimum Time to Finish the Race https://leetcode.com/contest/weekly-contest-282/problems/minimum-time-to-finish-the-race/

解説

この解説が分かりやすかった https://leetcode.com/problems/minimum-time-to-finish-the-race/discuss/1802444/C%2B%2B-Linear-time-DP-with-explanation

ポイント

アルゴリズム

• 問題文からdp[n+1]がdp[n]から導けそうなことに気づく
• 問題文から漸近式を導く
  • タイヤを交換するしない
  • さかのぼって交換する場合もタイヤの連続使用回数の上界で縛れること
• オーダを落とすための制約（タイヤの連続使用回数の上界がchangeTimeとfi * ri(x-1)から導かれる）

実装

• int32超え(2e9)の扱い