Merge Operations for Minimum Travel Time
You are given a straight road of length l km, an integer n, an integer k, and two integer arrays, position and time, each of length n.
The array position lists the positions (in km) of signs in strictly increasing order, with position[0] = 0 and position[n - 1] = l.
Each time[i] represents the time (in minutes) required to travel 1 km between position[i] and position[i + 1].
You must perform exactly k merge operations. In one merge, you can choose any two adjacent signs at indices i and i + 1, with i > 0 and i + 1 < n, and:
- Update the sign at index
i + 1so that its time becomestime[i] + time[i + 1]. - Remove the sign at index
i.
Return the minimum total travel time (in minutes) to travel from 0 to l after exactly k merges.
Example 1
Input
l = 10, n = 4, k = 1, position = [0,3,8,10], time = [5,8,3,6]Output
62Merging the signs at indices 1 and 2 gives positions [0, 8, 10] and times [5, 11, 6], for total travel time 8 * 5 + 2 * 11 = 62, which is minimum.
Example 2
Input
l = 5, n = 5, k = 1, position = [0,1,2,3,5], time = [8,3,9,3,3]Output
34Merging the signs at indices 1 and 2 gives positions [0, 2, 3, 5] and times [8, 12, 3, 3], for total travel time 2 * 8 + 1 * 12 + 2 * 3 = 34, which is minimum.
Constraints
- 1 <= l <= 10^5
- 2 <= n <= min(l + 1, 50)
- 0 <= k <= min(n - 2, 10)
- position.length == n
- position[0] = 0 and position[n - 1] = l
- position is sorted in strictly increasing order.
- time.length == n
- 1 <= time[i] <= 100
- 1 <= sum(time) <= 100