LC 2188. 完成比赛的最少时间
https://leetcode-cn.com/contest/weekly-contest-282/problems/minimum-time-to-finish-the-race/
这题有两个关键点，一个关键点考虑清楚了对时间复杂度有把握，另外一个就是对实现细节有帮助。
如果一直使用某个轮胎的话，那么肯定会存在某个时间点应该放弃。并且这个时间点并不会很长，因为 `r >= 2` 而 `changeTime <= 10^5`. 如果两次耗时超过 `changeTime + f` 的话，那么完全可以直接丢弃这个轮胎，使用这个新轮胎。为了保险起见，可以将这个时间点定在 `T=20` 次之后。
另外一个就是，如果我们认为第一次使用就考虑 `changeTime` 的话，那么之后叠加起来就会更加容易。得到结果之后，减去第一次的 `changeTime` 就好了。
最终我们可以得到 `best[T]` 表示跑T圈的最短耗时是多少，然后就是一个动态规划问题。
class Solution:
def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
n = len(tires)
cost = [changeTime] * n
factor = [1] * n
T = 20
best = [0] * T
for t in range(T):
for i in range(n):
cost[i] += tires[i][0] * factor[i]
factor[i] *= tires[i][1]
best[t] = min(cost)
dp = [1 << 30] * (1 + numLaps)
dp[0] = 0
for i in range(numLaps):
for t in range(T):
j = i + t + 1
if j <= numLaps:
dp[j] = min(dp[j], dp[i] + best[t])
return dp[numLaps] - changeTime