OpenJudge

4080:Huffman编码树

总时间限制:
1000ms
内存限制:
65536kB
描述

构造一个具有n个外部节点的扩充二叉树,每个外部节点Ki有一个Wi对应,作为该外部节点的权。使得这个扩充二叉树的叶节点带权外部路径长度总和最小:

                                     Min( W1 * L1 + W2 * L2 + W3 * L3 + … + Wn * Ln)

Wi:每个节点的权值。

Li:根节点到第i个外部叶子节点的距离。

编程计算最小外部路径长度总和。

输入
第一行输入一个整数n,外部节点的个数。第二行输入n个整数,代表各个外部节点的权值。
2<=N<=100
输出
输出最小外部路径长度总和。
样例输入
4
1 1 3 5
样例输出
17
全局题号
6939
添加于
2014-04-27
提交次数
1719
尝试人数
679
通过人数
613

Other language verions

您的评价 很水 简单 一般 较难 变态
  • 标签(多个标签用空格分隔):
  • 常用标签:
    递归   动态规划   贪心   搜索   枚举   模拟   数学   字符串处理   几何   高精度计算   图论  

共有9人评分

33.3%
11.1%
22.2%
33.3%
0.0%

已有的标签

递归(2) 哈夫曼树(2) 贪心(1) 图论(1) 文兄最帅(1)