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

看板Grad-ProbAsk作者 (傷神客)時間16年前 (2010/03/20 17:28), 編輯推噓5(5推 0噓 5→)
留言10則, 3人參與, 最新討論串2/4 (看更多)
※ 引述《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)
推
03/20 17:31, , 1F
恩~這樣符合題意 那(b)(c)有idea嗎?
03/20 17:31, 1F
→
03/20 17:33, , 2F
沒 我看過人家的解答書是寫用平分的, 不過我只能囧XD
03/20 17:33, 2F
推
03/20 17:35, , 3F
噢也是..平方可能會有極值差很多 剛沒想到= ="
03/20 17:35, 3F
→
03/20 17:36, , 4F
分
03/20 17:36, 4F
→
03/20 17:37, , 5F
它的平分不只是單純切割 還多了逼近XD
03/20 17:37, 5F
→
03/20 17:38, , 6F
不過由於學過dp後, 我對這種作法抱持著懷疑的態度XD
03/20 17:38, 6F
推
03/20 17:40, , 7F
有逼近的話那應該可以吧?
03/20 17:40, 7F
推
03/20 17:42, , 8F
這樣的做法就很接近找中位數然後分割L,R
03/20 17:42, 8F
推
03/20 18:17, , 9F
要怎麼紀錄是哪一個分割產生difference最小
03/20 18:17, 9F
→
03/20 20:17, , 10F
怎麼記錄? 直接找最小的就好啦
03/20 20:17, 10F
‣ 更多 privatewind 的文章
文章代碼(AID): #1Bf9KjxI (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 2 之 4 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共4篇)
‣ 更多 privatewind 的文章
文章代碼(AID): #1Bf9KjxI (Grad-ProbAsk)