討論串[問題] 數值合併
共 15 篇文章
內容預覽:
版上強者很多, 所以我又來問問題了. 有一系列的數字, 每次挑兩個相鄰的數字合併. 合併的數字按照原來順序插入序列之中, 合併的代價為 s , s 為兩個數字的和. 經過一連串的合併之後, 整個序列會只剩下一個值, 而總合併代價為 S. 問怎樣的合併動作, 總合併代價會是最小. 範例一:. 3 4
(還有237個字)
內容預覽:
看到 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]..
(還有256個字)
內容預覽:
假設有這樣一個數列. 10 7 2 4 12 6. 用 huffman algorithm. 10 7 6 12 6 cost : 6. 10 7 12 12 cost : 12. 12 12 17 cost : 17. 24 17 cost : 24. 41 cost : 41. Total Co
(還有289個字)
內容預覽:
嗯, 看到這個 case, 給了我一個靈感 (先 po 出來看看). Huffman 找值最小的兩個來合併,. 這裡似乎要找相鄰和最小的兩數來合併.. 比如 10+7, 7+2, 2+4, 4+12, 12+6, 所以先拿 2,4 來合併.. 然後 update heap 時, 要將影響到的鄰居一併
(還有1609個字)