P1880 [NOI1995] Merging Stones

Along the circumference of a circular track, there are $N$ piles of stones. We want to merge the stones into one pile in some order. Each time, we can only choose two adjacent piles and merge them into a new pile; the number of stones in the new pile is recorded as the score for that merge. Design an algorithm to compute the minimal total score and the maximal total score for merging $N$ piles into $1$ pile.

The first line contains the positive integer $N$, the number of piles. The second line contains $N$ integers; the $i$-th integer $a_i$ denotes the number of stones in the $i$-th pile.

Output a total of $2$ lines. The first line is the minimal total score, and the second line is the maximal total score.

Constraints: $1 \leq N \leq 100$, $0 \leq a_i \leq 20$. Translated by ChatGPT 5