Re: [問題] 數值合併
※ 引述《windows2k (KERORO軍曹)》之銘言：
: 版上強者很多, 所以我又來問問題了
我不是強者
只是口試完等畢業 & 當兵的閒人
看完推文中的投影片
把裡面的東西再重述一次
解這個問題的步驟主要有兩個：
1. 找 right minimal (R.M.)
2. 重排序列
這兩個動作要重覆至|S| = 1
R.M. 的定義：
A pair of leaves pi-1,pi is right minimal (briefly R.M.) if
(i) 1 < i <= n
(ii) pi-2 + pi-1 >= pi-1 + pi
(iii) pi-1 + pi < pj-1 + pj for all j>i
: 範例一:
: 3 4 5 (3,4) 合併 代價 7
: 7 5 (7,5) 合併 代價 12
: 12 總代價 19
step 1: R.M. = (3,4), merge後 S = {7, 5}, cost = 7
step 2: 重排 S, S = {5, 7}, R.M. = (5,7), merge後 S = {12}, cost = 12
total cost = 19
圖例：
原數列： 3 4 5
找RM並合併： 7 5 (此時3, 4各被加一次)
重排 5 7
找RM並合併： 12 (此時3, 4, 5各被加一次)
故合併方法為： ((3,4),5)
: 範例二:
: 5 3 4 5 (5,3) 合併 代價 8
: 8 4 5 (4,5) 合併 代價 9
: 8 9 (8,9) 合併 代價 17
: 17 總代價 34
step 1: R.M. = (3,4), merge後 S={5, 7, 5}, cost = 7
step 2: 重排S, S={5, 5, 7}, R.M. = (5,5), merge後 S = {10, 7}, cost = 10
step 3: 重排S, S={7, 10}, R.M. = (7, 10), merge後 S = {17}, cost = 17
total cost = 34
圖例：
原數列： 5 3 4 5
找RM並合併： 5 7 5 (此時3, 4各被加一次)
重排： 5 5 7
找RM並合併： 10 7 (此時5, 5各被加一次)
重排： 7 10
找RM並合併： 17 (此時3, 4, 5, 5各被加一次)
故合併方法為 ((5,3),(4,5))
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.202.72
※ 編輯: sandwichC 來自: 140.114.202.72 (07/18 14:35)
討論串 (同標題文章)