Re: [問題] 數值合併
※ 引述《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
其實有個演算法大家可以試看看..不一定最快但是可以找出optimal sol
以5 3 4 5來說 先對兩個node 算出cost 會得到
8 4 5 cost:8
5 7 5 cost:7
5 3 9 cost:9
然後再對那些cost裡面抓最小cost繼續做
所以現在seq 變成: 5 7 5 cost:7
repeat:
12 5 cost: 7 + 12
5 12 cost: 7 + 12
etc...
這樣的話complexity time:
repeat n times:
對每兩個node做compute(n) +
所有node丟到heap 並建出min heap(nlogn)
從min heap pop min cost(1)
total : n*nlogn
--
離最快的lag 還有一段距離...
想法可參考A-star algorithm
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.143.222.166
推
07/12 08:37, , 1F
07/12 08:37, 1F
→
07/12 08:37, , 2F
07/12 08:37, 2F
討論串 (同標題文章)