※ 引述《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