Re: [理工] [algo]-中央96-資工所

[FRAXIS (喔喔)]

※ 引述《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
推 privatewind:我也是這樣想 只是我不確定有沒有更好的方法XD
→ privatewind:如果考試我沒其它寫法 就會寫像這樣XD
推 ie925155:(2)不是要minimize嗎? 為什麼是找max??
→ FRAXIS:他是要Minimize the Maximum difference
→ FRAXIS:我那個Max是在算Maximum Difference..
→ privatewind:算出每一個Maximum Difference 後, 再取最小的~