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