Tap here to switch tabs
Problem
Submissions

Problem: Minimum Cost to Cut a Stick

Minimum Cost to Cut a Stick asks you to cut a stick at every listed position, where each cut costs the current segment length. Return the lowest total cost by choosing the cut order.

Statement

You are given a stick of length n with positions labeled from 00 to n. You must perform a cut at every position listed in cuts.

When you cut a stick segment, the cost of that cut equals the current length of the segment being cut. After making a cut, the segment is split into two smaller segments, and future cuts are applied to the appropriate resulting segment.

Return the minimum total cost to perform all cuts in cuts, where you may choose the order of cuts.

Constraints:

  • 2≤2 \leq n ≤106\leq 10^6

  • 1≤1 \leq cuts.length $\leq \min(n −- 11, 100)100)

  • 1≤1 \leq cuts[i] ≤\leq n −- 11

  • All integers in cuts are distinct.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Cost to Cut a Stick

Minimum Cost to Cut a Stick asks you to cut a stick at every listed position, where each cut costs the current segment length. Return the lowest total cost by choosing the cut order.

Statement

You are given a stick of length n with positions labeled from 00 to n. You must perform a cut at every position listed in cuts.

When you cut a stick segment, the cost of that cut equals the current length of the segment being cut. After making a cut, the segment is split into two smaller segments, and future cuts are applied to the appropriate resulting segment.

Return the minimum total cost to perform all cuts in cuts, where you may choose the order of cuts.

Constraints:

  • 2≤2 \leq n ≤106\leq 10^6

  • 1≤1 \leq cuts.length $\leq \min(n −- 11, 100)100)

  • 1≤1 \leq cuts[i] ≤\leq n −- 11

  • All integers in cuts are distinct.