推 Fenikso:模擬一樣是O(D)啊 不會比較慢 10/14 09:03
推 Fenikso:我回一篇好了.. 10/14 09:08
→ AmosYang: 能提示一下嗎? :) 10/14 09:08
※ 引述《bleed1979 (十三)》之銘言：
: http://www.spoj.pl/problems/ALL/
: 推 Fenikso:模擬題. 一開始兩片選一片放, 之後的動作全部固定 10/14 02:58
: → Fenikso:各模擬一次取比較小的就是了 10/14 02:59
因為 0<=D<=100000 ，建 tree 應該不會爆 out of memory , 所以
1. 一面讀 input 就一面建 dependency tree, 一面建 tree 一面記得 tree 的高度
root node 是來自第一片 DVD 的 package 的 tree 放一邊,
同時記得目前最高的 tree
root node 是來自第二片 DVD 的 package 的 tree 放一邊,
同時記得目前最高的 tree
2. 資料讀完後，把第一組最高的 tree 與 第二組最高的 tree 拿出來比高度
比較高的 tree 的高度 +2 應該就是答案
如果兩棵樹一樣高，高度 +3 為答案
這樣應該是 O(D) 解, 應該會比直接模擬快
--
※ 發信站 :批踢踢實業坊(ptt.cc)
◆ From: 24.40.140.18
※ 編輯: AmosYang 來自: 24.40.140.18 (10/14 08:56)
直接模擬…最簡單的寫法會是 O( (n1+n2) * D )
應該可以把那個 D 壓下來，但大概沒辦法壓得跟上面說的 O(D) 一樣快
※ 編輯: AmosYang 來自: 24.40.140.18 (10/14 09:02)