Re: [問題] SPOJ 1774. All Discs Considered [ALL]

看板Prob_Solve (計算數學 Problem Solving)作者 (Zzz...)時間13年前 (2011/10/14 10:16), 編輯推噓1(101)
留言2則, 2人參與, 最新討論串3/3 (看更多)
※ 引述《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)

10/14 10:55, , 1F
有道理!
10/14 10:55, 1F

10/14 15:06, , 2F
這個方法是對的,已AC,修改最原po,並講解相關的眉角。
10/14 15:06, 2F
有人對“可省下 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)
文章代碼(AID): #1Ebvjg6v (Prob_Solve)
文章代碼(AID): #1Ebvjg6v (Prob_Solve)