S****k
发帖数: 81 | 1 N个序列, 两两合并成一个序列。假设合并两个长度为L1和L2的序列需要L1+L2时间。设
计一个最优合并顺序。例如：合并长度为10,30,60的序列，最佳顺序是10＋30；40＋60
；总共花费140. 算法不难，不过需要数学证明其正确性。 | A*********c
发帖数: 430 | 2 贪心算法，优先合并短的，因为被合并的次数等于序列长度时间被算的次数。所以要最
小化时间，就要最小化长序列被合并的次数。
60
【在 S****k 的大作中提到】
: N个序列, 两两合并成一个序列。假设合并两个长度为L1和L2的序列需要L1+L2时间。设
: 计一个最优合并顺序。例如：合并长度为10,30,60的序列，最佳顺序是10＋30；40＋60
: ；总共花费140. 算法不难，不过需要数学证明其正确性。
| c*******7
发帖数: 438 | 3 假设数列是从 L1到Ln，因为每次是两个合并成一个，每次减少1个，所以需要n-1次合
并。
策略应该是每次选长度最小的两个数列合并。暂时想不到好的证明方法。 | d********e
发帖数: 239 | 4 哈夫曼code....用个最小堆就行了，取堆顶两次，每次把合并后的结果插入堆。堆空了
就是结束了。
60
【在 S****k 的大作中提到】
: N个序列, 两两合并成一个序列。假设合并两个长度为L1和L2的序列需要L1+L2时间。设
: 计一个最优合并顺序。例如：合并长度为10,30,60的序列，最佳顺序是10＋30；40＋60
: ；总共花费140. 算法不难，不过需要数学证明其正确性。
| b***e
发帖数: 1419 | 5 http://en.m.wikipedia.org/wiki/Huffman_coding
这个跟Huffman encoding的证明是一样的。
60
【在 S****k 的大作中提到】
: N个序列, 两两合并成一个序列。假设合并两个长度为L1和L2的序列需要L1+L2时间。设
: 计一个最优合并顺序。例如：合并长度为10,30,60的序列，最佳顺序是10＋30；40＋60
: ；总共花费140. 算法不难，不过需要数学证明其正确性。
| S********e
发帖数: 74 | 6 对，应该是huffman code的解法
【在 d********e 的大作中提到】
: 哈夫曼code....用个最小堆就行了，取堆顶两次，每次把合并后的结果插入堆。堆空了
: 就是结束了。
:
: 60
|
|
