※ 引述《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)