hardDynamic Programming 2DPure DSA~35 min
Minimum Cost to Cut a Plank at Marked Points
A plank of length n must be cut at a set of marked positions. The cost of any single cut equals the current length of the piece being cut. You may perform the cuts in any order. Minimize total cost.
Problem
Given an integer n (plank from 0 to n) and an array cuts of positions to cut, the cost of one cut is the length of the piece it falls in. After a cut the piece splits in two. Choose an order to perform all cuts that minimizes total cost; return that minimum.
Input
An integer n and an array cuts of distinct positions strictly between 0 and n.
Output
An integer: the minimum total cutting cost.
Constraints
- 2 <= n <= 10^6
- 1 <= cuts.length <= 100
- 1 <= cuts[i] <= n - 1, all distinct.
Examples
Example 1
Input
n = 7, cuts = [1,3,4,5]
Output
16
A good order totals 16; naive left-to-right costs more.
Example 2
Input
n = 9, cuts = [5,6,1,4,2]
Output
22
The optimal ordering of cuts costs 22.