力扣6011、完成比赛的最少时间

题目

给你一个下标从 0 开始的二维整数数组 tires ，其中 tires[i] = [fi, ri] 表示第 i 种轮胎如果连续使用，第 x 圈需要耗时 fi * ri(x-1) 秒。

比方说，如果 fi = 3 且 ri = 2 ，且一直使用这种类型的同一条轮胎，那么该轮胎完成第 1 圈赛道耗时 3 秒，完成第 2 圈耗时 3 * 2 = 6 秒，完成第 3 圈耗时 3 * 22 = 12 秒，依次类推。
同时给你一个整数 changeTime 和一个整数 numLaps 。

比赛总共包含 numLaps 圈，你可以选择 任意 一种轮胎开始比赛。每一种轮胎都有 无数条 。每一圈后，你可以选择耗费 changeTime 秒 换成 任意一种轮胎（也可以换成当前种类的新轮胎）。

请你返回完成比赛需要耗费的 最少 时间。

 

示例 1：

输入：tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
输出：21
解释：
第 1 圈：使用轮胎 0 ，耗时 2 秒。
第 2 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
第 3 圈：耗费 5 秒换一条新的轮胎 0 ，然后耗时 2 秒完成这一圈。
第 4 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
总耗时 = 2 + 6 + 5 + 2 + 6 = 21 秒。
完成比赛的最少时间为 21 秒。

示例 2：

输入：tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
输出：25
解释：
第 1 圈：使用轮胎 1 ，耗时 2 秒。
第 2 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
第 3 圈：耗时 6 秒换一条新的轮胎 1 ，然后耗时 2 秒完成这一圈。
第 4 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
第 5 圈：耗时 6 秒换成轮胎 0 ，然后耗时 1 秒完成这一圈。
总耗时 = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 秒。
完成比赛的最少时间为 25 秒。
 

提示：

• 1 <= tires.length <= 100000
• tires[i].length == 2
• 1 <= fi, changeTime <= 1e5
• 2 <= ri <= 1e5
• 1 <= numLaps <= 1000

思路

• 轮胎 比做 物品，圈数 比做 背包容量
• 轮胎数量无限制，换一次轮胎和轮胎连续使用消耗的时间 比作 体积
• 求出连续跑N圈消耗的最少时间，每个轮胎可能在跑第i圈达到时间最优。
• 假定使用每种轮胎前都要换轮胎

• 定义dp[i]表示第i圈消耗的最少时间
  定义mintimes[i]表示一种轮胎跑第i圈时间最优，也就是时间最短
  

动态转移方程

// 跑到第i圈，第 i 圈 前面的 j圈是从第i - j + 1圈换轮胎重新跑到第i圈
dp[i] = min(dp[i], dp[i - j] + mintimes[j]);

题解

#define N 18
// 一个轮胎最多连续跑N圈就得换轮胎，N由数据大小可以算出

#define min(a, b) \
    ((a) > (b) ? (b) : (a))

int minimumFinishTime(int** tires, int tiresSize, int* tiresColSize, int changeTime, int numLaps){
    int mintimes[N + 1]; //一种轮子跑i圈 的 最少时间
    memset(mintimes, 0x3f, sizeof(int) * (N+1));
    for (int i = 0; i < tiresSize; ++i) { //枚举轮子
        long long f = tires[i][0], r = tires[i][1], fr = f + changeTime;
        for (int j = 1, sum = fr; fr > f; ++j) { //啥情况退出循环，
            mintimes[j] = min(mintimes[j], sum);
            f *= r;
            sum += f;
        }
    }

    int dp[numLaps + 1];
    memset(dp, 0x3f, sizeof(int) * (numLaps + 1));
    dp[0] = 0;
    for (int i = 1; i <= numLaps; ++i) {
        for (int j = 1; j <= min(N, numLaps) && j <= i; ++j) {
            dp[i] = min(dp[i], dp[i - j] + mintimes[j]);
        }
    }
    return dp[numLaps] - changeTime; //开始多换了一次轮胎
}