1007: 电报
题目描述
你有一条消息需要通过电报发送给你的朋友。
在发送电报时，你可以传输两种符号：“.”和“-”。
你需要找到一种方式编码消息中的字符，意即把消息中的每个字符对应为一个仅由“.”和“-”组成的字符串。
对于一种编码方式，如果没有两个字符对应的字符串使得其中一个字符对应的字符串是另一个字符对应的字符串的前缀，我们就称这种编码方式为合法的编码方式。
例如，如果你将A编码为“.-”，则你不能将B编码为“.-.”，但你可以将B编码为“-.-”。
在电报中，发送一个“.”需要一个单位时间，发送一个“-”需要两个单位时间。
你需要找到一种合法的编码方式使得该条消息的发送时间最短。
输入
第一行一个整数N，表示该条消息里会出现N种字符。
第二行N个整数，表示每种字符的出现次数。
输出
样例输入 复制
#1
3
2 1 1
#2
4
1 2 3 4
#3
4
1 2 2 3
#4
5
1 1 1 1 1
#5
5
2 2 2 2 2样例输出 复制
#1
9
#2
27
#3
22
#4
17
#5
34提示
【样例解释】
对于样例1：
第一个字符编码为“.”，第二个字符编码为“-.”，第三个字符编码为“--”，用时最短，为2x1+1x(2+1)+1x(2+2)=9个单位时间
对于样例2：
第一个字符编码为“.--”，第二个字符编码为“.-.”，第三个字符编码为“..”，第四个字符编码为“-”，用时最短，为1x(1+2+2)+2x(1+2+1)+3x(1+1)+4x2=27个单位时间
对于样例3：
第一个字符编码为“--”，第二个字符编码为“.-”，第三个字符编码为“-.”，第四个字符编码为“..”，用时最短，为1x(2+2)+2x(1+2)+2x(2+1)+3x2=22个单位时间
【数据范围】
对于15%的数据，1<=N<=15
对于40%的数据，1<=N<=100
对于70%的数据，1<=N<=400
对于100%的数据，1<=N<=750，每种字符出现的次数在1到10^5之间