2188. Minimum Time to Finish the Race

You are given a 0-indexed 2D integer array tires where tires[i] = [fi, ri] indicates that the ith tire can finish its xth successive lap in fi * ri(x-1) seconds.

• For example, if fi = 3 and ri = 2, then the tire would finish its 1st lap in 3 seconds, its 2nd lap in 3 2 = 6 seconds, its 3rd lap in 3 22 = 12 seconds, etc.
  You are also given an integer changeTime and an integer numLaps.

The race consists of numLaps laps and you may start the race with any tire. You have an unlimited supply of each tire and after every lap, you may change to any given tire (including the current tire type) if you wait changeTime seconds.

Return the minimum time to finish the race.

class Solution {
    int getUse(int ct, vector<int>& tire) {
        int use = 1, r = tire[1];
        long long start = tire[0];
        while(true) {
            if(start * r >= ct + start) return use;
            start *= r;
            use++;
        }
        return -1;
    }
    int knapsack(int& ct, vector<int>& t, int lab) {
        vector<int> dp(lab + 1, 987654321);
        dp[0] = -ct;
        for(int i = 0; i < t.size(); i++) {
            for(int j = i + 1; j < dp.size(); j++) {
                dp[j] = min(dp[j], dp[j-i-1] + t[i] + ct);
            }
        }
        return dp.back();
    }
public:
    int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {
        sort(tires.begin(), tires.end());
        vector<vector<int>> newTire {tires[0]};
        vector<int> use{min(numLaps, getUse(changeTime, newTire.back()))};
        int maxUse = use.back();
        for(int i = 0; i < tires.size(); i++) {
            if(tires[i][0] == newTire.back()[0]) continue;
            if(tires[i][1] >= newTire.back()[1]) continue;
            newTire.push_back(tires[i]);
            use.push_back(min(numLaps, getUse(changeTime, tires[i])));
            maxUse = max(use.back(), maxUse);
        }
        int n = newTire.size();

        vector<int> cost(maxUse, INT_MAX);
        for(int i = 0; i < n; i++) {
            int useSum = 0;
            for(int j = 0; j < use[i]; j++) {
                useSum += newTire[i][0] * pow(newTire[i][1],j);
                cost[j] = min(useSum, cost[j]);
            }
        }

        return knapsack(changeTime, cost, numLaps);
    }
};