[理工] 108交大資演

[hank1321 (knah1321)]

想問一題minimal intermediate sum的
好像是第21題，題組題
題目大概是說，4+1+2+3可以插入3組括號變成((4+1)+(2+3))=((5)+(5))=10 然後5+5+10=
20
但也可以寫成(4+((1+2)+3)) 會跑出3,6,10,sum=19
19就比20小

然後問題是要找4,4,8,5,4,3,5的最小解

我算是
(((4+4)+8)+(5+((4+3)+5)))
=(((8)+8)+(5+((7)+5)))
=((16)+(5+(12)))
=(16+(17))
=(33)
分別跑出8,7,16,12,17,33，相加起來是93
可是答案好像是給91
不知道自己盲點到底在哪裡...
有大大可以提供一下解出91的想法嗎 感恩

一題就整題組爆 好痛嗚嗚

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.92.113
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1550485751.A.557.html
→ h3882249: 用哈輔慢呢
推 cks116: 4+4  8  5+4  3+5
→ cks116: 我是想讓局部盡量小 且數大小平均一點
推 magic83v: 用huffman作法
推 skyHuan: 那時候想好久是Huffman還是像matrix chain那樣還是想不出
→ skyHuan: 來QQ
推 Dora5566: 不能huffman吧  最小的兩個又不一定相鄰
推 aeiou335: 要用dp
推 eric21489: 同2樓作法 這樣91沒錯 我忘了加最後一次...
推 ko330: 第二行5跟5合阿 就是用ㄏ夫曼= =
推 ChunagMT: 我以為數字不能對調…
推 uttc: 也想知道91怎麼出來的
推 eric21489: 8+9+8+16+17+33
推 ruifan: 不是插括號 可以任選兩個加
推 ruifan: 題目沒有說要相鄰吧
→ S2067030: 現場完全來不及做 在家算的方法跟2樓一樣
→ eric21489: 我覺得不能動吧
推 ruifan: 等等 我又看了一次題目 好像是插括號沒錯
→ eric21489: 只是剛好huffman答案一樣就是了
推 maple205: 不能換位置吧
推 cvn21: 這題就是霍夫曼啦
推 ChunagMT: 不能換位子答案還會一樣嗎？
推 YeaPa: 2樓應該是對的 我現場也是算93 QQQ
→ S2067030: 題目是4.4.8.5.4.3.5
→ S2067030: (((4+4)+8)+ ((5+4)+(3+5)))
→ S2067030: 8+9+8+16+17+33=91
推 f101202: https://i.imgur.com/pvjPoNW.jpg
→ f101202: 題目應該讓霍夫曼出來的答案不一樣..這樣就被某些人撿到
→ f101202: 了==
推 magic83v: 真的==撿到一題 那個turnaround time*4也撿到
推 Dora5566: 辣基= =
噓 Dora5566: 不知道多少人用huffman賺分
推 uttc: 這用赫夫曼的話第一步是3+4 不會對 例如我QQ
→ f101202: 這運氣真的有點屌..錯錯得正
→ uttc: 哦 原來是偷換了位子會對....
→ gaowei16: 沒說不能換吧==
→ gaowei16: 不過我沒換算91 第二次算81 直接失智
→ gaowei16: 喔對 剛剛又看了一下 不能換 答案真根霍夫曼一樣==
推 skyHuan: 霍夫慢到底怎麼選，我一開始用霍夫曼想沒辦法選點就用DP
→ skyHuan: 了，但試了一下覺得太麻煩就跳過最後來不及用猜的><
推 f101202: Sky葛格錯誤的方法不要學>\\\\<
推 ekids1234: 抱歉借串問，資演有一題算 array memory address 的，
→ ekids1234: 大家都算的跟解答一樣？人在外沒帶考卷
→ Dora5566: 樓上 一樣
→ hank1321: 一樣
推 Rioronja: 用dp解
推 ekids1234: https://i.imgur.com/uUQnwYs.jpg
→ ekids1234: 想詢問一下我想錯了哪邊 QQ
推 young60509: 跟ekid大一樣寫E  不懂為啥錯QQ
→ uttc: 題目要16進位 68是10進位
推 tinhanho: f大的DP 1,4 是42吧
推 tinhanho: 1,6 是71吧