※ 引述《Fenikso (ばかちーは俺の嫁)》之銘言： : ※ 引述《AmosYang (Zzz...)》之銘言： : : 推 Fenikso:模擬一樣是O(D)啊 不會比較慢 10/14 09:03 : : 推 Fenikso:我回一篇好了.. 10/14 09:08 : : → AmosYang: 能提示一下嗎? :) 10/14 09:08 : 其實本質上是個dfs XD : 1. 先建dependency graph (不是tree 雖然這不太重要XD) : 這張圖要用adjacency list存 : 對每個input (x, y) 從y連一條有向邊到x : 同時統計每個點的in degree : 到這裡為止是linear : 以下假設先放第一片, 放第二片的時候同理 其實，如果要這樣作的話 (而不是在建 dependency graph 時就順便算答案) 連換片重跑模擬都不用，可以省 50% 的計算 :D 基本上我們只需要 dependency graph 裡的最長 path 的長度 以及 “如果有一條以上 path 的長度等於 max length 是否這些 path 都起始於同一張 DVD? (或著，是否這些 path 都停止於同一張 DVD? 這兩個條件都可以用) 如果所有 max length 的 path 都起始 (或停止) 於同一張 DVD 那答案就是 max length +2 反之，則答案為 max length +3 -- ※ 發信站 :批踢踢實業坊(ptt.cc) ◆ From: 24.40.140.18 這個神奇的 +3 來自於原題裡第二個範例 長度 L 的 dependency path 要換片 L 次 如果有兩條以上長度 maxL 的 dependency path ，從同一張 DVD 出發 則還是一樣只需要換片 L 次; 加上題目要的 +2，答案就是 L+2 如果有兩條長度 maxL 的 dependency path 一條從 DVD 1 出發 另一條從 DVD 2 出發 則只需要換片 L+1 次; 加上題目要的 +2，答案就是 (L+1)+2 = L+3 ※ 編輯: AmosYang 來自: 24.40.140.18 (10/14 10:22) 有人對“可省下 50% 運算”有疑問，在此試著說明的更清楚些 :) 1. 當你把 dependency list 讀完後，你可以建出一堆 dependency tree 2. 我們先只看一棵 tree, 我們會發現，如果這棵 tree 高度為 h 那我們就得要換片 h 次 也就是說，如果一棵樹高度為 h1, 另一棵樹高度為 h2 且 h2 > h1 ; 那我們可以不用去管高度為 h1 的那棵樹 因為我們一定要換片換至少 h2 次 是故，我們只對最高的樹有興趣 3. 最高的樹可能不止一棵, 以下有兩種情形要考慮 在此設最高的樹的高度為 H 3.1 所有高度為 H 的樹頂都是在同一張 DVD 上 那換片 H 次就可以收工，傳回答案 H+2 ( +2 來自於原題目的要求) 3.2 所有高度為 H 的樹頂不在同一張 DVD 上 不管從哪片 DVD 開始，我們都得換片 H+1 次 是故，傳回答案 (H+1)+2 從模擬(simulate)的角度切入這題的話，的確是得跑模擬兩次 但如果從 dependency list 的本質切入的話，就會發現題目只在乎 dependency path 的長度，對 dependency path 的起點/終點並不在乎 是故不用跑完整的模擬，在模擬的過程中計算各 dependency path 的長度就可以了 而計算這長度，並不需要去區分起點，因為不管從哪張 DVD 開始 path 本身不會變，所以 path 長度也不會變 希望這樣有清楚一些 :) ※ 編輯: AmosYang 來自: 24.40.140.18 (10/15 12:02)