作者joywilliamjo (joywilliamjoy)
看板Grad-ProbAsk
标题Re: [理工] 108 台大资工 资演 对答案
时间Fri Dec 25 18:15:45 2020
想请教其中的两题
第一个是第5-a的第3题
https://i.imgur.com/tNV1Egl.jpg
写的时候并不知道in place的意思
写完之後上网看了一下维基百科
上面写说quick-sort常被描述为inplace演算法，但实际操作的时候需要一个O(logn)的sp
ace来支援quicksort中的递回
所以这题到底要写T还是F@@
然後是最後一题的DP
https://i.imgur.com/erjeBip.jpg
想问一下有比较快速的计算方式吗还是真的得每一次每一次下去算..
到长度6或7以上的时候其实蛮多种组合要去试的
还是没有就只能慢慢算？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.138.19.142 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1608891347.A.272.html
1F：推 cossetannie: 递回的空间不算12/25 19:01
2F：推 mathtsai: Qsort写exchange 所以没有用到额外空间 是inplace12/25 19:05
3F：→ mathtsai: dp列出定义还有recurrence 剩下就只能乖乖算12/25 19:08
4F：→ mathtsai: 总共10项 从左填到右 每次最多3个规则 应该不会太久(?12/25 19:37
我算的时候是怕新加入的会可以跟前面的有新的融合所以每一个长度都有重算
写的当下快没时间，从右边开始往回推greedy刚好有28就写了
※ 编辑: joywilliamjo (223.138.19.142 台湾), 12/25/2020 22:50:05
5F：→ mathtsai: 这样你没办法说明第2题12/25 23:51
没有要说明啊
写答案就好了
题目意思是这样吧@@？
※ 编辑: joywilliamjo (223.138.19.142 台湾), 12/26/2020 00:53:48
6F：推 alex391a: 最後一题那个我记得计算量算少的吧（？ 12/26 01:26
7F：推 alex391a: 你是不是用纯暴力法没用DP 12/26 01:28
8F：推 alex391a: 举个例长度7的时候末端只有#2 #7可以 所以你就算 长度五 12/26 01:33
9F：→ alex391a: +#2 长度四+#7 选小的就是了 12/26 01:33
10F：→ mathtsai: 不能这样算 也有可能长度9+三角形 12/26 01:48
11F：→ mathtsai: 所以还是要从左边一格一格填 12/26 01:49
12F：→ mathtsai: 如果题目设计好一点的话 没有greedy choice property 12/26 01:50
13F：→ mathtsai: 按照楼主的算法应该会算错 12/26 01:50
14F：推 alex391a: 对啦还有 长度六+三角形 这样就好了啊 12/26 08:51
16F：→ alex391a: 大概是酱 DP基本题 12/26 16:56
17F：→ alex391a: 楼上我是说从头开始写 我只是举例怎麽取dp的概念而已XD 12/26 16:58
18F：推 gash55025502: 最後一题不用想太复杂吧 观察可以得到每种转换最多 12/27 02:16
19F：→ gash55025502: 只能让一个图案减少1的cost(如#1,4,5,7) 所以就从 12/27 02:16
20F：→ gash55025502: 最前面的图案开始找看看能不能用#1,4,5,7去转换 找 12/27 02:16
21F：→ gash55025502: 得到就继续往下找直到所以图案都用#1,4,5,7转换过 12/27 02:16
22F：→ mathtsai: alex那个是正解 12/27 02:26