Re: [理工] [algo]-中央96-資工所
※ 引述《privatewind (傷神客)》之銘言：
: ※ 引述《assassin88 (魚躍龍門)》之銘言：
: : 題目：http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_96_01.pdf
: : 想請問一下第七題，不知道這一題該怎麼作答比較好呢？
: : 不是很懂他的題意 XDD
: : 麻煩解答了~thx
(a) 已經有人解了
(b) k=3的方法也是類似，假設你已經有(a)的演算法
固定第三人是負責從i起到最後的部份，也就是Si ~ Sn的部份
然後S1 ~ Si的部份用(a)的演算法求出最佳分配，設切點在j
那此狀況下最佳解就是
Max( |Si~Sn - S1~Sj|, |Si~Sn - Sj+1~Si-1|, |S1~Sj - Sj+1~Si-1| )
只要從1~i每個都去解一次，然後挑最小值就是解答..
所以只要O(n^2)
(c) 令F(n, k)= (A, B) 代表由S1~Sn分給k個人最佳分配中最大值為A最小值為B
F(1, 1) = (S1, S1) <- Base case
F(i, j) = (A, B)
where A = Min( A', Sm~Si )
B = Max( B', Sm~Si )
F(m-1, j-1) = (A', B')
m是可以使Max( A', Sm~Si) - Min(B', Sm~Si)最小的值
應該是這樣吧..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
推
03/20 22:52, , 1F
03/20 22:52, 1F
→
03/20 22:53, , 2F
03/20 22:53, 2F
推
03/20 23:19, , 3F
03/20 23:19, 3F
→
03/20 23:29, , 4F
03/20 23:29, 4F
→
03/20 23:30, , 5F
03/20 23:30, 5F
→
03/20 23:58, , 6F
03/20 23:58, 6F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 4 篇)：