A granary keeps n grain piles standing in a row, each with a positive integer size. You must combine them into a single pile by repeatedly picking two piles that are currently adjacent in the row and merging them into one pile whose size is the sum of the two. Each merge costs exactly the size of the newly formed pile.
Different merge orders can lead to different total costs. Report the minimum total cost to reduce the whole row to one pile.
Line 1: an integer n, the number of piles.
Line 2: n space-separated positive integers, the pile sizes from left to right.
A single integer: the minimum total merging cost (0 if there is only one pile).
Example 1
Input
3 1 2 3
Expected
9
Explanation
Merge 1 and 2 (cost 3) to get piles [3, 3], then merge those (cost 6): total 9. Any other order costs more.
Example 2
Input
4 1 1 1 1
Expected
8
Explanation
Merge into two piles of size 2 (cost 2 each), then merge the two size-2 piles (cost 4): 2 + 2 + 4 = 8, better than merging strictly left to right (which costs 9).
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →