作者march20 ()
看板Prob_Solve
标题Re: [问题] 数值合并
时间Sun Jul 9 02:55:24 2006
※ 引述《windows2k (KERORO军曹)》之铭言：
: 版上强者很多, 所以我又来问问题了
: 有一系列的数字, 每次挑两个相邻的数字合并
: 合并的数字按照原来顺序插入序列之中, 合并的代价为 s , s 为两个数字的和
: 经过一连串的合并之後, 整个序列会只剩下一个值, 而总合并代价为 S
: 问怎样的合并动作, 总合并代价会是最小
: 范例一:
: 3 4 5 (3,4) 合并 代价 7
: 7 5 (7,5) 合并 代价 12
: 12 总代价 19
: 范例二:
: 5 3 4 5 (5,3) 合并 代价 8
: 8 4 5 (4,5) 合并 代价 9
: 8 9 (8,9) 合并 代价 17
: 17 总代价 34
: 5 3 4 5 (3,4) 合并 代价 7
: 5 7 5 (5,7) 合并 代价 12
: 12 5 (12,5) 合并 代价 17
: 17 总代价 36
: 可见greedy algorithm并非最佳解
: 用Dynamic programming的话, 存在一个 O(n^3)的演算法
: 不过有一个 O(nlogn)的演算法, 却不得其门而入
看到 n log n , 大胆猜看看.
给定数列 S = {s_1, s_2, s_3, ... , s_n}
先造一个 L[0..n], 其中 L[x] = sum_{1<=i<=x} s_i
这样就可以简单地求到任意一组 s_x + ... + s_y = L[y] - L[x-1].
接下来 divide and conquer:
假设要求 s_x, ... , s_y 的最佳合并, 采 binary search 找出 s_x,...,s_y 的中位点 s_m
也就是 mid = [sum_{x<=i<=y} s_i]/2 的值落在 s_m 上.
urr, 简单来说 (!?), 也就是
[sum_{x <= i <= m-1} s_i]
< mid
<= [sum_{x <= i <= m} s_i]
我猜最佳合并法就是 s_x,...,s_m 和 s_(m+1),...,s_y 先各自合并, 接着再并起来.
(s_m 要归在左还是右, 似乎没那麽简单, 好像要看怎麽分两边和的差最小?)
还没验证过, 先 post 出来 XD.
: 有谁可以提示一下, 感激不尽
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 71.137.22.103