看板 [ Prob_Solve ]
討論串[問題] SPOJ 1774. All Discs Considered [ALL]
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
Re: [問題] SPOJ 1774. All Discs Considered [ALL]
推噓2(2推 0噓 1→)留言3則，0人參與, 最新作者AmosYang (Zzz...)時間13年前 (2011/10/14 08:51), 編輯資訊
1
0
1
內容預覽:
因為 0<=D<=100000 ，建 tree 應該不會爆 out of memory , 所以. 1. 一面讀 input 就一面建 dependency tree, 一面建 tree 一面記得 tree 的高度. root node 是來自第一片 DVD 的 package 的 tree 放一邊
(還有280個字)
#2
Re: [問題] SPOJ 1774. All Discs Considered [ALL]
推噓2(2推 0噓 2→)留言4則，0人參與, 最新作者Fenikso (ばかちーは俺の嫁)時間13年前 (2011/10/14 09:24), 編輯資訊
1
0
0
內容預覽:
其實本質上是個dfs XD. 1. 先建dependency graph (不是tree 雖然這不太重要XD). 這張圖要用adjacency list存. 對每個input (x, y) 從y連一條有向邊到x. 同時統計每個點的in degree. 到這裡為止是linear. 以下假設先放第一片,
(還有483個字)
#3
Re: [問題] SPOJ 1774. All Discs Considered [ALL]
推噓1(1推 0噓 1→)留言2則，0人參與, 最新作者AmosYang (Zzz...)時間13年前 (2011/10/14 10:16), 編輯資訊
0
0
0
內容預覽:
其實，如果要這樣作的話 (而不是在建 dependency graph 時就順便算答案). 連換片重跑模擬都不用，可以省 50% 的計算 :D. 基本上我們只需要 dependency graph 裡的最長 path 的長度. 以及 “如果有一條以上 path 的長度等於 max length. 是
(還有1117個字)
首頁
上一頁
1
下一頁
尾頁