作者hank1321 (knah1321)
看板Grad-ProbAsk
标题[理工] 108交大资演
时间Mon Feb 18 18:29:08 2019
想问一题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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1550485751.A.557.html
1F：→ h3882249: 用哈辅慢呢 02/18 18:35
2F：推 cks116: 4+4 8 5+4 3+5 02/18 18:36
3F：→ cks116: 我是想让局部尽量小 且数大小平均一点 02/18 18:37
4F：推 magic83v: 用huffman作法 02/18 18:37
5F：推 skyHuan: 那时候想好久是Huffman还是像matrix chain那样还是想不出 02/18 18:50
6F：→ skyHuan: 来QQ 02/18 18:50
7F：推 Dora5566: 不能huffman吧 最小的两个又不一定相邻 02/18 18:54
8F：推 aeiou335: 要用dp 02/18 18:57
9F：推 eric21489: 同2楼作法 这样91没错 我忘了加最後一次... 02/18 18:57
10F：推 ko330: 第二行5跟5合阿 就是用ㄏ夫曼= = 02/18 18:59
11F：推 ChunagMT: 我以为数字不能对调… 02/18 19:05
12F：推 uttc: 也想知道91怎麽出来的 02/18 19:11
13F：推 eric21489: 8+9+8+16+17+33 02/18 19:12
14F：推 ruifan: 不是插括号 可以任选两个加 02/18 19:14
15F：推 ruifan: 题目没有说要相邻吧 02/18 19:16
16F：→ S2067030: 现场完全来不及做 在家算的方法跟2楼一样 02/18 19:16
17F：→ eric21489: 我觉得不能动吧 02/18 19:18
18F：推 ruifan: 等等 我又看了一次题目 好像是插括号没错 02/18 19:18
19F：→ eric21489: 只是刚好huffman答案一样就是了 02/18 19:20
20F：推 maple205: 不能换位置吧 02/18 19:23
21F：推 cvn21: 这题就是霍夫曼啦 02/18 19:42
22F：推 ChunagMT: 不能换位子答案还会一样吗？ 02/18 19:43
23F：推 YeaPa: 2楼应该是对的 我现场也是算93 QQQ 02/18 19:45
24F：→ S2067030: 题目是4.4.8.5.4.3.5 02/18 19:56
25F：→ S2067030: (((4+4)+8)+ ((5+4)+(3+5))) 02/18 19:57
26F：→ S2067030: 8+9+8+16+17+33=91 02/18 19:57
28F：→ f101202: 题目应该让霍夫曼出来的答案不一样..这样就被某些人捡到 02/18 20:45
29F：→ f101202: 了== 02/18 20:45
30F：推 magic83v: 真的==捡到一题 那个turnaround time*4也捡到 02/18 21:46
31F：推 Dora5566: 辣基= = 02/18 23:48
32F：嘘 Dora5566: 不知道多少人用huffman赚分 02/18 23:52
33F：推 uttc: 这用赫夫曼的话第一步是3+4 不会对 例如我QQ 02/19 00:50
34F：→ f101202: 这运气真的有点屌..错错得正 02/19 02:11
35F：→ uttc: 哦 原来是偷换了位子会对.... 02/19 02:12
36F：→ gaowei16: 没说不能换吧== 02/19 08:18
37F：→ gaowei16: 不过我没换算91 第二次算81 直接失智 02/19 08:19
38F：→ gaowei16: 喔对 刚刚又看了一下 不能换 答案真根霍夫曼一样== 02/19 08:23
39F：推 skyHuan: 霍夫慢到底怎麽选，我一开始用霍夫曼想没办法选点就用DP 02/19 08:44
40F：→ skyHuan: 了，但试了一下觉得太麻烦就跳过最後来不及用猜的>< 02/19 08:44
41F：推 f101202: Sky葛格错误的方法不要学>\\\\< 02/19 11:28
42F：推 ekids1234: 抱歉借串问，资演有一题算 array memory address 的， 02/19 13:10
43F：→ ekids1234: 大家都算的跟解答一样？人在外没带考卷 02/19 13:10
44F：→ Dora5566: 楼上 一样 02/19 13:33
45F：→ hank1321: 一样 02/19 14:14
46F：推 Rioronja: 用dp解 02/19 16:14
48F：→ ekids1234: 想询问一下我想错了哪边 QQ 02/19 19:45
49F：推 young60509: 跟ekid大一样写E 不懂为啥错QQ 02/19 20:54
50F：→ uttc: 题目要16进位 68是10进位 02/19 21:06
51F：推 tinhanho: f大的DP 1,4 是42吧 12/24 21:29
52F：推 tinhanho: 1,6 是71吧 12/24 21:35