This is a problem that came to me by chance and I don't know how to solve it
Given n positive integers
Choose any two integers a and b and merge them into a+b, the cost of the operation is max(a,b)
Repeat the operation until there is only one number left, find the minimum possible cost
I found a similar problem on the web, and in that one, the cost of the operation is a+b.
In that problem, the solution is to choose the smallest two integers in every operation.
Unfortunately, it can't work in this problem.
1 2 2 3
If we always choose the smallest two integers
the process will be 1 2 2 3 -> 2 3 3 -> 3 5 -> 8 and the cost is 2+3+5=10
However,if we do like this: 1 2 2 3 -> 2 2 4 -> 4 4 -> 8, the cost will be 3+2+4=9