↓Skip to main content
  1. Posts/

LeetCode-2188 完成比赛的最少时间

·1 min·
Table of Contents

LeetCode-2188 完成比赛的最少时间 #

Solution 1 #

完成比赛相当于把圈数划分成连续的若干段, 其总时间等于各子段所需要的时间加上 “划分” (也就是题中的换胎操作) 所需要的时间. 定义 $cost[i]$ 也就是连续跑 $i$ 圈所花费的最少时间. 需要注意的是, 由指数的特性, 如果 $cost[i] \geq cost[i - 1] + cost[1] + changeTime$ , 那么就没必要计算 $cost[i + 1], … cost[n]$ 了.
代码如下:

class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        def geometric_series_sum(r, k):
            return k if r == 1 else int((1 - r**k) / (1 - r))
        
        cost = [inf] * (numLaps + 1)
        for i in range(1, numLaps + 1):
            cost[i] = min(
                cost[i],
                min([f * geometric_series_sum(r, i) for f, r in tires]),
            ) 
            if cost[i] > cost[i - 1] + cost[1] + changeTime:
                break

        dp = [inf] * (numLaps + 1)
        for i in range(1, numLaps + 1):
            dp[i] = cost[i]
            for j in range(1, i):
                dp[i] = min(dp[i], dp[j] + cost[i - j] + changeTime)
        return dp[numLaps]