Readme

3538.Merge-Operations-for-Minimum-Travel-Time

我们比较容易想到令dp[i][k]表示前进至第i个标记时、且做了k次合并的最短时间。此时为了计算时间，我们需要知道上一处合并点的位置j，以及从j到i的效率（即单位长度所用的时间）。考虑到约束条件1 <= sum(time) <= 100​​​​​​，这时一个可以遍历的数字，所以我们就可以将其作为第三个维度。即我们定理dp[i][k][v]表示前进至第i个标记时、恰做了k次合并、且从i开始的效率是v的情况下，所用的最短时间。

写出上述表达式之后，我们发现想要计算dp[i][k][v]，如果只遍历上一个停留点j的位置是不够的，因为从j往后到i的效率也是未知的，无法计算从j到i所花的时间。似乎状态转移陷入了僵局。

其实基于dp[i][k][v]，我们发现对未来的状态进行推断更容易一些。我们同样遍历下一个停留点的位置j，那么从i往后到j所需要的时间是基于v且已知的t = v*(dist[j]-dist[i])。此外，从j点往后的效率就是v2=time[i:j]的区间和，也是已知的。于是，我们就可以用dp[i][k][v] + t来尝试更新dp[j][k+j-i-1][v2]的值。

这样的时间复杂度就是50*18*100*40 = 3e6数量级，可以通过。