Re: [問題] SPOJ 1774. All Discs Considered [ALL]
看板Prob_Solve (計算數學 Problem Solving)作者AmosYang (Zzz...)時間13年前 (2011/10/14 10:16)推噓1(1推 0噓 1→)留言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
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)
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 3 之 3 篇):
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12