[理工] 台大資演

[ssssIssss (O_O)]

QQQQ

遞迴推導出答案算是證明嗎，想請教一下m(_ _)m

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.46.18
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486778658.A.E52.html
推 hut326521: 哪一題R
第一大題～～ 第一小題我忘記再證明f(n)<=c*nlogn（忘記答案了反正我只有遞迴推導出
來...）
※ 編輯: ssssIssss (223.140.46.18), 02/11/2017 10:07:25
推 shortid: 不敢用master method 展開代入給他
本來想說回頭再證結果寫太久，一直寫到下課才把題目都寫完Orz
※ 編輯: ssssIssss (223.140.46.18), 02/11/2017 10:08:41
推 BEARlol: 第一題是不是用bfs 或dfs就好了啊沒有cycle
→ BEARlol: 我說後面證明第一題
推 opu456: 遞迴證明比較好吧 用master還要證master是對的比較完整
→ opu456:  不過教授應該不會這麼摳哈哈
所以不用再用定義驗證一次嗎

但是第三小題我用遞迴樹，感覺就是必須要再驗證惹
※ 編輯: ssssIssss (223.140.46.18), 02/11/2017 10:15:21
→ ken52011219: 用DAG 解決
→ ken52011219: 四題我都用substitution
Lawler?
推 HEroKuma: 忘記要optimal 用Dp解= =……
→ ken52011219: 最後一題b 原本已經寫好答案了 默默地邊看著 那個倒
→ ken52011219: 扣分數  邊擦掉QQ
推 lion83395: 前兩題本來用master 但最後寫展開 會怕
→ ken52011219: DP 的時間複雜度為多少O(2^nn^2)嗎？
推 hut326521: 借問一下第一題的證明是不是沒寫到就直接沒分啊QQ 寫
→ hut326521: 到最後有一些來不及回頭證
推 leoone: QQ最後一題A用bellman ford去亂掰惹
推 lion83395: 證明我都沒寫..錯了代價太高
→ lion83395: 4-A我用dijkstra變形去解
推 aa06697: 我想問硬體34題 前面是要填在34還是填在12 ==？
→ aa06697: 照題號「順序」 是什麼意思啊...
推 HEroKuma: DP只要O(n^2) 可以過濾很多不會發生的case
推 BBbaba: 問一下LCS 那題 3C是要填什麼啊？
推 yorunohoshi: 我也是用中央資工出的那個node weight Dijkstra去做
→ yorunohoshi: ，不過速度輸DAG的Bellmen-ford logV0.0
推 lion83395: len[i,j]?
推 sickle30: 我寫len[i,j] 朋友說是A[i,j] XD
推 leoone: 我寫prev[i,j]....
推 BBbaba: 我寫ai…
推 Dust2080: 我也寫ai
推 endinfierce: ai
ai，我覺得len全部印出來沒什麼意義QQ
※ 編輯: ssssIssss (223.140.46.18), 02/11/2017 13:24:43
→ qooo8435: 好像是ai 他print在遞迴下面一行
推 HEroKuma: 遞迴找到第一個共同的字元ai然後印出來
※ 編輯: ssssIssss (140.112.25.106), 02/11/2017 13:34:34
推 brad84622: ai一票
推 cschenptt: 上面兩小題 請問各位寫多少?
len[i-1, j-1]+1

(A, xxx, i-1, j-1)

xxx是我忘了題目參數順序了，大概就是都減一
※ 編輯: ssssIssss (223.140.103.29), 02/11/2017 14:58:11
推 hihihi45: 我現在才看到有倒扣  已經掰下去了...
→ BBbaba: prev
推 cschenptt: 第一小題後面沒寫+1...QQ 那請問前面四個bigO大大寫多
→ cschenptt: 少
其實我是覺得不會倒扣耶，畢竟沒給機制怎麼扣都不太合理
※ 編輯: ssssIssss (223.140.103.29), 02/11/2017 15:12:40
→ BBbaba: 我寫 lg3(2) n nlg n lglgnlgn
→ lion83395: 考的時候看題目好像有要求長度 現在想想好像ai比較合理
→ lion83395:  算了QQ
別想了，快準備下一科！
※ 編輯: ssssIssss (114.44.199.115), 02/11/2017 15:59:26
推 YuxiWen: cities我先賦予權重r(u, v)+c(v), 然後用dijikstra解,
→ YuxiWen:  最後每一個cities+c(captal), 突然想到我好像手誤吧c(ca
→ YuxiWen: ptal)寫成c(A), 還沒說明c(A)是什麼
→ YuxiWen: 已哭...
推 cyc4542015: 用dijikstra感覺怪怪的 因為每次多經過一個邊會有多co
→ cyc4542015: st 應該是不能用greedy
→ cyc4542015: 我是用bellman
若是DAG那應該都是可以的，看什麼會optimal吧？
→ w181496: 資演那題我以為是DAG上的DP最短路欸0.0
DAG還要DP嗎？還是Lawler即可？
推 eric7144: 我是先用dfs 求出topological sort 在跑bellman ford 可
→ eric7144: 以是O(v+e)
那relaxing依序呢QQ
※ 編輯: ssssIssss (223.140.111.120), 02/11/2017 20:53:42
推 joejoejoe: 用dfs求出topological sort不會miss掉一些可能嗎@@?
只是更方便快速吧～ 因為圖多很多限制條件了
推 joejoejoe: 查了一下發現真的要用topolgical sort....台大資工掰掰
※ 編輯: ssssIssss (223.136.177.94), 02/12/2017 07:39:06