Re: [理工] 108 台大資工 資演 對答案

[joywilliamjo (joywilliamjoy)]

想請教其中的兩題
第一個是第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://www.ptt.cc/bbs/Grad-ProbAsk/M.1608891347.A.272.html
推 cossetannie: 遞迴的空間不算
推 mathtsai: Qsort寫exchange 所以沒有用到額外空間 是inplace
→ mathtsai: dp列出定義還有recurrence 剩下就只能乖乖算
→ mathtsai: 總共10項 從左填到右 每次最多3個規則 應該不會太久(?
我算的時候是怕新加入的會可以跟前面的有新的融合所以每一個長度都有重算
寫的當下快沒時間，從右邊開始往回推greedy剛好有28就寫了
※ 編輯: joywilliamjo (223.138.19.142 臺灣), 12/25/2020 22:50:05
→ mathtsai: 這樣你沒辦法說明第2題
沒有要說明啊
寫答案就好了
題目意思是這樣吧@@？
※ 編輯: joywilliamjo (223.138.19.142 臺灣), 12/26/2020 00:53:48
推 alex391a: 最後一題那個我記得計算量算少的吧（？
推 alex391a: 你是不是用純暴力法沒用DP
推 alex391a: 舉個例長度7的時候末端只有#2 #7可以 所以你就算 長度五
→ alex391a: +#2 長度四+#7 選小的就是了
→ mathtsai: 不能這樣算 也有可能長度9+三角形
→ mathtsai: 所以還是要從左邊一格一格填
→ mathtsai: 如果題目設計好一點的話 沒有greedy choice property
→ mathtsai: 按照樓主的算法應該會算錯
推 alex391a: 對啦還有 長度六+三角形 這樣就好了啊
推 alex391a: https://i.imgur.com/fHJQXKE.jpg
→ alex391a: 大概是醬 DP基本題
→ alex391a: 樓上我是說從頭開始寫 我只是舉例怎麼取dp的概念而已XD
推 gash55025502: 最後一題不用想太複雜吧 觀察可以得到每種轉換最多
→ gash55025502: 只能讓一個圖案減少1的cost(如#1,4,5,7) 所以就從
→ gash55025502: 最前面的圖案開始找看看能不能用#1,4,5,7去轉換 找
→ gash55025502: 得到就繼續往下找直到所以圖案都用#1,4,5,7轉換過
→ mathtsai: alex那個是正解