[理工] 台大資演

看板Grad-ProbAsk作者 (O_O)時間7年前 (2017/02/11 10:04), 7年前編輯推噓29(29推 0噓 24→)
留言53則, 23人參與, 最新討論串1/1
QQQQ 遞迴推導出答案算是證明嗎，想請教一下m(_ _)m -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.46.18 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486778658.A.E52.html
推
02/11 10:06, , 1F
哪一題R
02/11 10:06, 1F
第一大題～～ 第一小題我忘記再證明f(n)<=c*nlogn（忘記答案了反正我只有遞迴推導出 來...） ※ 編輯: ssssIssss (223.140.46.18), 02/11/2017 10:07:25
推
02/11 10:07, , 2F
不敢用master method 展開代入給他
02/11 10:07, 2F
本來想說回頭再證結果寫太久，一直寫到下課才把題目都寫完Orz ※ 編輯: ssssIssss (223.140.46.18), 02/11/2017 10:08:41
推
02/11 10:11, , 3F
第一題是不是用bfs 或dfs就好了啊沒有cycle
02/11 10:11, 3F
→
02/11 10:12, , 4F
我說後面證明第一題
02/11 10:12, 4F
推
02/11 10:12, , 5F
遞迴證明比較好吧 用master還要證master是對的比較完整
02/11 10:12, 5F
→
02/11 10:12, , 6F
不過教授應該不會這麼摳哈哈
02/11 10:12, 6F
所以不用再用定義驗證一次嗎 但是第三小題我用遞迴樹，感覺就是必須要再驗證惹 ※ 編輯: ssssIssss (223.140.46.18), 02/11/2017 10:15:21
→
02/11 10:16, , 7F
用DAG 解決
02/11 10:16, 7F
→
02/11 10:17, , 8F
四題我都用substitution
02/11 10:17, 8F
Lawler?
推
02/11 10:17, , 9F
忘記要optimal 用Dp解= =……
02/11 10:17, 9F
→
02/11 10:20, , 10F
最後一題b 原本已經寫好答案了 默默地邊看著 那個倒
02/11 10:20, 10F
→
02/11 10:20, , 11F
扣分數 邊擦掉QQ
02/11 10:20, 11F
推
02/11 10:20, , 12F
前兩題本來用master 但最後寫展開 會怕
02/11 10:20, 12F
→
02/11 10:24, , 13F
DP 的時間複雜度為多少O(2^nn^2)嗎？
02/11 10:24, 13F
推
02/11 12:13, , 14F
借問一下第一題的證明是不是沒寫到就直接沒分啊QQ 寫
02/11 12:13, 14F
→
02/11 12:13, , 15F
到最後有一些來不及回頭證
02/11 12:13, 15F
推
02/11 12:15, , 16F
QQ最後一題A用bellman ford去亂掰惹
02/11 12:15, 16F
推
02/11 12:18, , 17F
證明我都沒寫..錯了代價太高
02/11 12:18, 17F
→
02/11 12:19, , 18F
4-A我用dijkstra變形去解
02/11 12:19, 18F
推
02/11 12:21, , 19F
我想問硬體34題 前面是要填在34還是填在12 ==？
02/11 12:21, 19F
→
02/11 12:22, , 20F
照題號「順序」 是什麼意思啊...
02/11 12:22, 20F
推
02/11 12:23, , 21F
DP只要O(n^2) 可以過濾很多不會發生的case
02/11 12:23, 21F
推
02/11 12:59, , 22F
問一下LCS 那題 3C是要填什麼啊？
02/11 12:59, 22F
推
02/11 13:03, , 23F
我也是用中央資工出的那個node weight Dijkstra去做
02/11 13:03, 23F
→
02/11 13:03, , 24F
，不過速度輸DAG的Bellmen-ford logV0.0
02/11 13:03, 24F
推
02/11 13:06, , 25F
len[i,j]?
02/11 13:06, 25F
推
02/11 13:13, , 26F
我寫len[i,j] 朋友說是A[i,j] XD
02/11 13:13, 26F
推
02/11 13:17, , 27F
我寫prev[i,j]....
02/11 13:17, 27F
推
02/11 13:17, , 28F
我寫ai…
02/11 13:17, 28F
推
02/11 13:19, , 29F
我也寫ai
02/11 13:19, 29F
推
02/11 13:21, , 30F
ai
02/11 13:21, 30F
ai，我覺得len全部印出來沒什麼意義QQ ※ 編輯: ssssIssss (223.140.46.18), 02/11/2017 13:24:43
→
02/11 13:25, , 31F
好像是ai 他print在遞迴下面一行
02/11 13:25, 31F
推
02/11 13:27, , 32F
遞迴找到第一個共同的字元ai然後印出來
02/11 13:27, 32F
※ 編輯: ssssIssss (140.112.25.106), 02/11/2017 13:34:34
推
02/11 14:36, , 33F
ai一票
02/11 14:36, 33F
推
02/11 14:51, , 34F
上面兩小題 請問各位寫多少?
02/11 14:51, 34F
len[i-1, j-1]+1 (A, xxx, i-1, j-1) xxx是我忘了題目參數順序了，大概就是都減一 ※ 編輯: ssssIssss (223.140.103.29), 02/11/2017 14:58:11
推
02/11 15:02, , 35F
我現在才看到有倒扣 已經掰下去了...
02/11 15:02, 35F
→
02/11 15:02, , 36F
prev
02/11 15:02, 36F
推
02/11 15:02, , 37F
第一小題後面沒寫+1...QQ 那請問前面四個bigO大大寫多
02/11 15:02, 37F
→
02/11 15:02, , 38F
少
02/11 15:02, 38F
其實我是覺得不會倒扣耶，畢竟沒給機制怎麼扣都不太合理 ※ 編輯: ssssIssss (223.140.103.29), 02/11/2017 15:12:40
→
02/11 15:14, , 39F
我寫 lg3(2) n nlg n lglgnlgn
02/11 15:14, 39F
→
02/11 15:32, , 40F
考的時候看題目好像有要求長度 現在想想好像ai比較合理
02/11 15:32, 40F
→
02/11 15:32, , 41F
算了QQ
02/11 15:32, 41F
別想了，快準備下一科！ ※ 編輯: ssssIssss (114.44.199.115), 02/11/2017 15:59:26
推
02/11 18:05, , 42F
cities我先賦予權重r(u, v)+c(v), 然後用dijikstra解,
02/11 18:05, 42F
→
02/11 18:05, , 43F
最後每一個cities+c(captal), 突然想到我好像手誤吧c(ca
02/11 18:05, 43F
→
02/11 18:05, , 44F
ptal)寫成c(A), 還沒說明c(A)是什麼
02/11 18:05, 44F
→
02/11 18:06, , 45F
已哭...
02/11 18:06, 45F
推
02/11 19:34, , 46F
用dijikstra感覺怪怪的 因為每次多經過一個邊會有多co
02/11 19:34, 46F
→
02/11 19:34, , 47F
st 應該是不能用greedy
02/11 19:34, 47F
→
02/11 19:34, , 48F
我是用bellman
02/11 19:34, 48F
若是DAG那應該都是可以的，看什麼會optimal吧？
→
02/11 20:02, , 49F
資演那題我以為是DAG上的DP最短路欸0.0
02/11 20:02, 49F
DAG還要DP嗎？還是Lawler即可？
推
02/11 20:04, , 50F
我是先用dfs 求出topological sort 在跑bellman ford 可
02/11 20:04, 50F
→
02/11 20:04, , 51F
以是O(v+e)
02/11 20:04, 51F
那relaxing依序呢QQ ※ 編輯: ssssIssss (223.140.111.120), 02/11/2017 20:53:42
推
02/11 21:15, , 52F
用dfs求出topological sort不會miss掉一些可能嗎@@?
02/11 21:15, 52F
只是更方便快速吧～ 因為圖多很多限制條件了
推
02/11 21:23, , 53F
查了一下發現真的要用topolgical sort....台大資工掰掰
02/11 21:23, 53F
※ 編輯: ssssIssss (223.136.177.94), 02/12/2017 07:39:06
‣ 更多 ssssIssss 的文章
文章代碼(AID): #1Odd4YvI (Grad-ProbAsk)