推 olen0622: a 差不多 b 證明費氏堆積有最好的時間表現 詳細我好懶XD 12/13 15:51
推 gary70812: DAG不是最快嗎 12/13 15:58
→ TMDTMD2487: 這是DAG的最短路徑搜尋吧 12/13 18:05
→ TMDTMD2487: 可以在V+E的時間完成 12/13 18:06
→ TMDTMD2487: Direct Acyclic Graph 12/13 18:07
→ TMDTMD2487: 先對圖做拓譜排序 再依照排序順序做relax 12/13 18:07
→ TMDTMD2487: 拓譜排序用dfs 每當 finish就把點放到排序的前端 12/13 18:09
→ TMDTMD2487: Topology Sort : O(|V|+|E|) 12/13 18:10
→ TMDTMD2487: 對每個點做relax O(|V|) 12/13 18:10
推 leoone: 不知為何當初寫這題我會用bellman-ford去解 == 12/13 18:25
推 gary70812: 想問T大，雖知dag最快沒錯，但證明的部分你會怎麼下手 12/13 18:36
→ gary70812: ？直接比較其他algo的複雜度？ 12/13 18:36
推 alan23273850: 這題要用dag，不要用dijkstra，會沒分數 12/13 18:46
推 TMDTMD2487: 證明直接說我不會XD 不過配分15一定要掰一下 12/13 23:37
→ TMDTMD2487: 畢竟資料量就已經是O(V+E)了我想掰一下應該不會太低 12/13 23:38
→ TMDTMD2487: 我覺得這種證明應該沒幾個人寫得出來別怕 12/13 23:39
→ alan23273850: 這年的證明不能掰，會倒扣，看一下原本考卷就知道了 12/13 23:40
→ alan23273850: 雖然看題幹的風格很明顯知道是哪位大老出的，但跟 12/13 23:41
→ alan23273850: 往年的考古風格差異太大，我是覺得鑑別度不太高 12/13 23:41
→ alan23273850: 第一面簡單到有基本概念就會寫，第二面大家如果都不 12/13 23:42
→ alan23273850: 敢寫證明的話，分數就只有50,60,70三種，我是拿60 12/13 23:42
→ alan23273850: 而且一般演算法的課也不太教證明，遇到這種考卷就放 12/13 23:43
→ alan23273850: 開心一點，反正大家分數都差不多 12/13 23:44
→ TMDTMD2487: 幹這份會倒扣歐XD 那拿10分就好了 機掰考卷 12/13 23:54
→ ken52011219: 我當時是寫DAG這份應該只扣最後一小題空著的分數 12/13 23:57
→ ken52011219: 至於DAG的algo當時我有背 順便加減分析一下分數就到 12/13 23:58
→ ken52011219: 手了 12/13 23:58
推 gary70812: 我有看到ken大心得說台大資演85猛 12/14 00:31
謝謝大家！那我知道了，我會再補足DAG的知識，謝謝！
(聽到大家都不會證我就放心了XDD)
※ 編輯: defsrisars (61.231.54.199), 12/14/2017 03:39:39
→ aggress5566: 我想問個問題 這題這樣出有什麼用意嗎 我第一眼以為 12/14 04:16
→ aggress5566: 要考dp + greedy這種 12/14 04:17
→ aggress5566: oops 我看懂了 那當我沒問QQ 12/14 04:20