Merging Chapters at Minimum Cost
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
A novel is stored as N chapter files in a fixed order; file i has size sizes[i]. You may merge two adjacent files
into one, which costs the sum of their sizes (the merged file has that size too). Return the minimum total cost to end up
with a single file.
Examples
| sizes | result |
|---|---|
[40, 30, 30, 50] | 300 |
[1, 100, 1] | 203 |
[7] | 0 |
Example 1 — merge 40+30 and 30+50, then the two halves: (starting in the middle costs 310).
Example 2 — the two 1s are not adjacent, so .
Example 3 — nothing to merge.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(sizes: int[]) → long
Constraints
-
sizes.length -
sizes[i] - The answer may not fit in 32 bits.
Expected complexity
- Time
- O(N^2)
- Space
- O(N^2)
Examples
| sizes | Expected |
|---|---|
[40,30,30,50] | 300 |
[1,100,1] | 203 |
[7] | 0 |
Hint
Hint
The interval DP dp[i][j] = min_k (dp[i][k] + dp[k+1][j]) + S(i, j) is . Because the range-sum cost satisfies the
quadrangle inequality and is monotone, Knuth's optimization applies: the best split satisfies
opt[i][j-1] <= opt[i][j] <= opt[i+1][j], so only that range of k needs to be scanned, and the scans telescope to
in total. Trying every k exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 236 ms | estimated |
| C++ (GCC, gnu++23) | 236 ms | derived |
| Python 3.13 | 4714 ms | derived |
| Java 25 | 1200 ms | derived |
| Kotlin 2.4 (JVM) | 1472 ms | estimated |
| C# 14 (.NET 10) | 1472 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |