#P10889. [2015yali备战noi]code
[2015yali备战noi]code
题目描述
给定有序字母集 中每个字母的出现频率,给每个字母分配一个二进制串作为编码,满足:
- 任何一个字母的编码都不是另一个字母编码的前缀。
- 按照字母的原顺序排列,各字母的编码按字典序递增。
编码方案的权重是
$$\sum_{c\in\chi} \operatorname{length}(\operatorname{code}(c))\operatorname{frequency}(c).$$求满足以上条件的最小权重。
例如,对于依次排列的 ,编码 同时满足前缀和顺序条件; 满足前缀条件; 满足顺序条件。若频率分别为 ,第一种方案的权重为 。
输入格式
第一行一个整数 (),表示字母个数。第二行按顺序给出 个字母的频率,每个频率均为 到 之间的整数。
输出格式
输出一个整数,表示最小权重。
样例
4
5 1 3 7
29
样例的一种最优编码为 ,权重为 。