作者sandwichC (没回应=挂站)
看板Prob_Solve
标题Re: [问题] 数值合并
时间Tue Jul 18 14:05:32 2006
※ 引述《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)