Merge Operations for Minimum Travel Time - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3538. Merge Operations for Minimum Travel Time
Hard
50 Points
Array
Dynamic Programming
Prefix Sum
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:
Return the minimum total travel time (in minutes) to travel from 0 to l after exactly k merges.
Examples
Example 1
Input: l = 10, n = 4, k = 1, position = [0,3,8,10], time = [5,8,3,6]
Output: 62
Explanation:
Merge the signs at indices 1 and 2. Remove the sign at index 1, and change the time at index 2 to 8 + 3 = 11 .
Example 2
Input: l = 5, n = 5, k = 1, position = [0,1,2,3,5], time = [8,3,9,3,3]
Output: 34
Explanation:
Constraints
1 <= l <= 105
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
3538. Merge Operations for Minimum Travel Time
Hard
50 Points
Array
Dynamic Programming
Prefix Sum
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:
Return the minimum total travel time (in minutes) to travel from 0 to l after exactly k merges.
Examples
Example 1
Input: l = 10, n = 4, k = 1, position = [0,3,8,10], time = [5,8,3,6]
Output: 62
Explanation:
Merge the signs at indices 1 and 2. Remove the sign at index 1, and change the time at index 2 to 8 + 3 = 11 .
Example 2
Input: l = 5, n = 5, k = 1, position = [0,1,2,3,5], time = [8,3,9,3,3]
Output: 34
Explanation: