Readme

2188.Minimum-Time-to-Finish-the-Race

整体思想显然是DP。令dp[i]表示跑i圈的最小代价，那么它取决于最后一次换胎的选择。假设最后一次换胎跑了j圈，那么就有dp[i] = dp[i-j] + changTime + minTime[j]，其中j表示minTime[j]是在所有轮胎类型中跑j圈最快的时间。所以求解DP的过程大致是o(numLaps^2) = 1e6 的复杂度，可以接受。

那么预处理minTime需要多少时间呢？在有m种轮胎，如果把所有的minTime[j], j=1,2,3,...numLaps都计算的话，我们需要花o(m*numLaps)的时间，那就是1e8数量级，必然TLE。该如何改进呢？

事实上我们根据跑一圈的公式t = f*r^(x-1)，在不换胎的条件下，当x很大时，跑一圈的时间会指数级地增长。显然，当不换胎多跑一圈的时间大于换胎本身的时间时，无论对于任何轮胎，继续跑下去都是不合算的。通过尝试发现，我们在最极端的条件下，即f=1，r=2时，当x是第20圈的时候，跑一圈所花的时间就有2^19=5e5已经大于了changeTime的上限。所以无论对于什么轮胎，一次性跑20圈都是不划算的。因此在dp的转移方程里，我们对于minTime的下标不会超过20圈。

所以本题的DP计算是o(20*numLaps)，此外我们提前需要预处理minTime[20]需要o(20m)=2e6的时间。

以上的操作还会有TLE。进一步改进的方法是减少轮胎的种类。显然如果轮胎A的f参数和r参数都比轮胎B的大，那么轮胎A完全就可以忽略。所以我们可以将所有轮胎按照r参数递增排列，顺次检查这些轮胎时，如果发现任何一个轮胎的f值大于等于前面的轮胎，那么该轮胎就可以忽略。这样我们就可以大幅度地减少轮胎的种类。