作者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