Solutions CS101

Appearance

T3538.合并得到最小旅行时间 ​

dp, https://leetcode.cn/problems/merge-operations-for-minimum-travel-time/

给你一个长度为 l 公里的直路，一个整数 n，一个整数 k 和 两个 长度为 n 的整数数组 position 和 time 。

数组 position 列出了路标的位置（单位：公里），并且是 严格 升序排列的（其中 position[0] = 0 且 position[n - 1] = l）。

每个 time[i] 表示从 position[i] 到 position[i + 1] 之间行驶 1 公里所需的时间（单位：分钟）。

你 必须 执行 恰好 k 次合并操作。在一次合并中，你可以选择两个相邻的路标，下标为 i 和 i + 1（其中 i > 0 且 i + 1 < n），并且：

  • 更新索引为 i + 1 的路标，使其时间变为 time[i] + time[i + 1]。
  • 删除索引为 i 的路标。

返回经过 恰好 k 次合并后从 0 到 l 的 最小总旅行时间（单位：分钟）。

示例 1:

输入: l = 10, n = 4, k = 1, position = [0,3,8,10], time = [5,8,3,6]

输出: 62

解释:

  • 合并下标为 1 和 2 的路标。删除下标为 1 的路标，并将下标为 2 的路标的时间更新为 8 + 3 = 11。

  • 合并后：

    • position 数组：[0, 8, 10]
    • time 数组：[5, 11, 6]
  • 路段距离（公里）每公里时间（分钟）路段旅行时间（分钟）
    0 → 8858 × 5 = 40
    8 → 102112 × 11 = 22

  • 总旅行时间：40 + 22 = 62 ，这是执行 1 次合并后的最小时间。

示例 2:

输入: l = 5, n = 5, k = 1, position = [0,1,2,3,5], time = [8,3,9,3,3]

输出: 34

解释:

  • 合并下标为 1 和 2 的路标。删除下标为 1 的路标，并将下标为 2 的路标的时间更新为 3 + 9 = 12。

  • 合并后：

    • position 数组：[0, 2, 3, 5]
    • time 数组：[8, 12, 3, 3]
  • 路段距离（公里）每公里时间（分钟）路段旅行时间（分钟）
    0 → 2282 × 8 = 16
    2 → 31121 × 12 = 12
    3 → 5232 × 3 = 6

  • 总旅行时间：16 + 12 + 6 = 34 ，这是执行 1 次合并后的最小时间。

提示:

  • 1 <= l <= 10^5
  • 2 <= n <= min(l + 1, 50)
  • 0 <= k <= min(n - 2, 10)
  • position.length == n
  • position[0] = 0 和 position[n - 1] = l
  • position 是严格升序排列的。
  • time.length == n
  • 1 <= time[i] <= 100
  • 1 <= sum(time) <= 100

采用「三维DP」：

  • 状态 dp[b][i][j] 表示已保留了 b 个路标，且最后两个保留的路标索引分别为 i 和 j 时的最小花费。
  • 转移：从 (b,i,j) 枚举下一个保留 k>j，对应区间 j→k 的旅程时间为 (pos[k]-pos[j])*(ST[j]-ST[i])，其中 ST 是前缀和 ST[x]=∑_{l=1..x}time[l]，这个乘积即该区间总公里数乘上累积的每公里耗时。
  • 初始化 对于保留第 1 个（起点）和第 j 个形成第一段路程，dp[2][1][j] = (pos[j]-pos[1])*(ST[1]-ST[0])。
  • 最终答案为 dp[B][i][n] 中最小值，其中 B = n-k 且路标 n（终点）必保留。
python
from typing import List

class Solution:
    def minTravelTime(self, l: int, n: int, k: int, position: List[int], time: List[int]) -> int:
        # Number of landmarks initially: n, we keep B = n - k after merges
        B = n - k
        # 1-based indexing for convenience
        # positions: 1..n
        pos = [0] * (n + 1)
        for i in range(1, n + 1): pos[i] = position[i - 1]
        # times: 1..n, but time[n] unused
        t = [0] * (n + 1)
        for i in range(1, n + 1): t[i] = time[i - 1]
        # prefix sum of time for indices 0..n
        ST = [0] * (n + 1)
        for i in range(1, n + 1): ST[i] = ST[i - 1] + t[i]
        # dp[b][i][j]: minimum cost when we have chosen b kept landmarks,
        # and the last two kept indices are i (second last) and j (last). 1 <= i < j <= n
        INF = 10**18
        dp = [ [ [INF] * (n + 1) for _ in range(n + 1) ] for _ in range(B + 1) ]
        # Base: b = 2, landmarks 1 and j kept
        # cost of first block from 1 -> j: uses time[1], distance pos[j]-pos[1]
        for j in range(2, n + 1):
            dp[2][1][j] = (pos[j] - pos[1]) * (ST[1] - ST[0])
        # DP transitions
        for b in range(2, B):
            for i in range(1, n + 1):
                for j in range(i + 1, n + 1):
                    cost_ij = dp[b][i][j]
                    if cost_ij >= INF:
                        continue
                    # choose next kept k > j
                    for k_idx in range(j + 1, n + 1):
                        # cost for block from j -> k_idx: uses time sum = ST[j] - ST[i]
                        block_time = ST[j] - ST[i]
                        block_dist = pos[k_idx] - pos[j]
                        new_cost = cost_ij + block_dist * block_time
                        if new_cost < dp[b + 1][j][k_idx]:
                            dp[b + 1][j][k_idx] = new_cost
        # final answer: b = B, last kept must be n
        ans = INF
        for i in range(1, n):
            ans = min(ans, dp[B][i][n])
        return ans

# Example
if __name__ == '__main__':
    sol = Solution()
    print(sol.minTravelTime(10, 4, 1, [0,3,8,10], [5,8,3,6]))  # 62
    print(sol.minTravelTime(5, 5, 1, [0,1,2,3,5], [8,3,9,3,3]))  # 34