Merge neighbours

dynamic programming optimization

A text lies in n files in a row, and they have to be joined into one. Only two neighbouring files can be joined; a join costs as many characters as the resulting file has, and it takes the place of the two. In what order should they be joined for the total cost to be smallest?

The third test is the 370 stanzas of “Eugene Onegin” in the Russian original, each in a separate file.

Input

The first line holds n (1 ≤ n ≤ 1200). The second holds the file sizes a₁, …, a_n (1 ≤ a_i ≤ 10⁶).

Output

The smallest total cost. If there is one file, there is nothing to join: 0.

Examples

Example 1

Input

4
4 1 2 3

Output

Example 2

Input

1
7

Output

Limits

Time · Python: 5000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 8 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

The last join connects two files, each of which was joined from an interval of the original ones. So this is an interval DP: cost[i][j] = min_m (cost[i][m] + cost[m + 1][j]) + the sum of the interval. How much is that for n = 1200?

2Hint 2

About n³/6, three hundred million steps. The cost of an interval is its sum; for it the quadrangle inequality holds with equality, and it does not decrease when the interval is widened. What can then be said about the best point of the last join?

3The idea

Knuth's window: under these conditions the best point m for [i, j] lies between the best ones for [i, j − 1] and [i + 1, j] (Knuth, Yao). Try m only in this window, and the whole table costs O(n²).

4Walkthrough

Go over interval lengths from 2 to n. For the interval [i, j] the window runs from best[i][j − 1] to best[i + 1][j], cut down to j − 1; remember the best point in best[i][j]. For intervals of length 1 the best “point” is i itself. The tables are n² numbers: 1.4 million, 8 bytes each for the cost and 4 for the point.

4+Solution

5Complexity

O(n²): the windows of intervals of one length together cover at most 2n points. The cost is at most n · Σa ≈ 1.4 · 10¹², which fits in 64 bits.

6Common mistakes

Trying all m. This is wrong.py: on the 370 stanzas of “Onegin” it still finishes in time, on 1200 files it does not.
Huffman's greed. The two smallest can be joined only if they are neighbours. Huffman with arbitrary pairs does not apply here, and “join the lightest neighbouring pair” is not optimal: for 8, 8, 5, 7, 4 it gives 77, while the best order gives 75.
A window without cutting. best[i + 1][j] can equal j, while the join point for [i, j] must be less than j.
The order of the table. Ready answers are needed for intervals one shorter: go by lengths, not by the left end.

Algorithms behind it

DP Technique Knuth and divide-and-conquer optimisations 45 thousand towns on a map by population class: 3.5 million evaluations instead of five billion, because the best split is monotone. O(k · n log n) 2 problems DP Technique Interval DP The state is an interval [i, j], the transition is where to cut it: search trees, matrix chain order, sawing. O(n³) 2 problems