P9483 [NOI2023] Merging Books

Xiao C has $n$ books, each with a weight. He decides to merge them into one pile. In each merge, Xiao C can put one pile of books on top of another pile, so that they become one pile. If Xiao C puts the $i$-th pile onto the $j$-th pile, the stamina cost is **the weight of the $i$-th pile** plus **the sum of the wear values of the two piles**. Initially, each book forms its own pile and all wear values are $0$. Each time Xiao C merges two piles, the new pile’s wear value becomes **twice the larger wear value of the two piles plus one**, and its weight becomes **the sum of the weights of the two piles**. Your task is to design the merging order to minimize Xiao C’s stamina cost, and output this minimum cost.

**This problem has multiple test cases.** The first line contains a positive integer $t$, the number of test cases. Then for each test case: The first line contains a positive integer $n$, meaning there are $n$ books. The second line contains $n$ positive integers; the $i$-th number $w_i$ is the weight of the $i$-th book.

For each test case, output one integer per line, representing the minimum stamina required to merge the $n$ books into one pile.

**[Sample Explanation #1]** If Xiao C first merges the $4$ books in pairs, and then merges the two resulting piles into one pile, then the stamina costs of the first two merges are both $1$. For the third merge, he puts a pile of weight $2$ onto the other pile; both piles have wear value $1$, so the stamina cost is $2 + 1 + 1 = 4$. Therefore, under this plan, Xiao C’s total stamina cost is only $1 + 1 + 4 = 6$. It can be proven that, in the above example, $6$ is the minimum stamina cost. **[Constraints]** For all test cases: $1 \le t \le 10$, $1 \le n \le 100$, $1 \le w_i \le 10 ^ 9$. |Test Point ID|$n \le$|Special Property| |:-:|:-:|:-:| |$1 \sim 2$|$7$|No| |$3$|$11$|No| |$4$|$13$|No| |$5 \sim 6$|$22$|No| |$7 \sim 8$|$28$|No| |$9 \sim 13$|$50$|No| |$14$|$60$|No| |$15$|$70$|No| |$16$|$80$|No| |$17 \sim 18$|$100$|Yes| |$19 \sim 20$|$100$|No| Special property: it is guaranteed that $w_i = 1$. Translated by ChatGPT 5