6011. 完成比赛的最少时间

Link

https://leetcode-cn.com/contest/weekly-contest-282/problems/minimum-time-to-finish-the-race/

Meaning

1. tires[i] = {fi, ri} 表示第 i 种轮胎连续使用 x 圈，跑完该圈耗时 fi * ri^(x-1) 秒
2. changeTime 表示换一次轮胎的耗时
3. numLaps 表示需要完成的圈数
4. 每一种轮胎有无数条，每一圈后可以耗费 changeTime 的时间换一种轮胎（可以是当前种类新轮胎）
5. 求最小耗时
6. 1 <= tires.length <= 105
7. tires[i].length == 2
8. 1 <= fi, changeTime <= 105
9. 2 <= ri <= 105
10. 1 <= numLaps <= 1000

Solution

1. 如果每一圈都换一个新轮胎，总时间不超过 (numLaps) * (fi + changeTime) = 2e8 秒
2. 因为 ri >= 2，时间为指数增长，也就是用同一个轮胎不会超过 log(2e8) < 28 圈
3. 预处理出连跑 j 圈所需的最短时间 minSec[j]
4. 定义 f[i] 表示第 i 圈所需的最小耗时
5. 转移方程 f[i] = changeTime + min{f[i-j] + minSec[j]} ( 1 <= j <= min(i,27) )，表示第 i 圈的最短时间是连续使用同一个轮胎跑 j 圈而来的
6. 为了方便设 f[0] = -changeTime

Code

import java.util.Arrays;

class Solution {
    public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
        int inf = (int)2e8;
        int n = tires.length;
        int[] minSec = new int[30];
        int[] sumSec = new int[n];
        Arrays.fill(minSec, inf);
        for (int i = 1; i <= 27; i++) {
            for (int j = 0; j < n; j++) {
                sumSec[j] = Math.min(sumSec[j] + tires[j][0], inf);
                minSec[i] = Math.min(minSec[i], sumSec[j]);
                tires[j][0] = (int) Math.min((long)tires[j][0] * tires[j][1], inf);
            }
        }

        int[] f = new int[numLaps+1];
        Arrays.fill(f, inf);
        f[0] = -changeTime;
        for (int i = 1; i <= numLaps; i++) {
            for (int j = 1; j <= Math.min(i,27); j++) {
                f[i] = Math.min(f[i], f[i-j] + minSec[j]);
            }
            f[i] += changeTime;
        }
        return f[numLaps];
    }
}