1547. Minimum Cost to Cut a Stick¶
题目信息¶
- 题号:
1547
- 难度:
Hard
- 主题:
区间动态规划、排序、切割
- 原题:
- 重点:
每次切割成本等于当时所在木棍段的长度;可以任意安排切割顺序,求完成全部指定切口的最小总成本
题目重述¶
有一根长度为 n 的木棍,覆盖坐标 [0,n]。数组 cuts 给出必须切割的内部位置,所有位置互不相同。
每次在某个尚未切开的木棍段中执行一个指定切割,成本等于该段当前长度。请安排切割顺序,使完成全部切割的总成本最小,并返回该最小值。
2 <= n <= 10^6,1 <= cuts.length <= 100,每个切口严格位于 0 与 n 之间。
自建示例¶
先切靠近中间的位置可以降低后续成本:
输入:n = 7, cuts = [1,3]
输出:10
解释:先在 3 处切割成本 7,再在左段的 1 处切割成本 3,总计 10。
只有一个切口时成本就是整根木棍长度:
输入:n = 2, cuts = [1]
输出:2
解释:第一次也是唯一一次切割发生在长度为 2 的木棍上。