作者privatewind (傷神客)
看板Grad-ProbAsk
標題Re: [理工] [algo]-中央96-資工所
時間Sat Mar 20 17:28:10 2010
※ 引述《assassin88 (魚躍龍門)》之銘言：
: 題目：http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_96_01.pdf
: 想請問一下第七題，不知道這一題該怎麼作答比較好呢？
: 不是很懂他的題意 XDD
: 麻煩解答了~thx
假設x陣列代表每一個partition, n為元素個數 如:
x[0] x[1] x[2] x[3] x[4]
100 200 300 400 500
建立一個A陣列
A[i]=x[0]+x[1]+...+x[i]
對x而言, 可以有0~ i-1種分割點
x[0] | x[1] x[2] x[3] x[4]
x[0] x[1] | x[2] x[3] x[4]
x[0] x[1] x[2] | x[3] x[4]
x[0] x[1] x[2] x[3] | x[4]
D[i]代表x[0]~x[i]與x[i+1]~x[n-1] partition的difference
D[i]=| A[i] - (A[n-1]-A[i])|
D[i]=| A[n-1] - 2A[i] |
一樣用一個for loop 解決。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 120.107.174.109
※ 編輯: privatewind 來自: 120.107.174.109 (03/20 17:30)
推 assassin88:恩~這樣符合題意 那(b)(c)有idea嗎? 03/20 17:31
→ privatewind:沒 我看過人家的解答書是寫用平分的, 不過我只能囧XD 03/20 17:33
推 assassin88:噢也是..平方可能會有極值差很多 剛沒想到= =" 03/20 17:35
→ assassin88: 分 03/20 17:36
→ privatewind:它的平分不只是單純切割 還多了逼近XD 03/20 17:37
→ privatewind:不過由於學過dp後, 我對這種作法抱持著懷疑的態度XD 03/20 17:38
推 assassin88:有逼近的話那應該可以吧? 03/20 17:40
推 assassin88:這樣的做法就很接近找中位數然後分割L,R 03/20 17:42
推 ie925155:要怎麼紀錄是哪一個分割產生difference最小 03/20 18:17
→ privatewind:怎麼記錄? 直接找最小的就好啦 03/20 20:17