Kiraru's blog

By Kiraru, 4 months ago, In English

This is a problem that came to me by chance and I don't know how to solve it

  1. Given n positive integers

  2. Choose any two integers a and b and merge them into a+b, the cost of the operation is max(a,b)

  3. 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.

For example

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

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +41
  • Vote: I do not like it