※ 引述《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) 有人对“可省下 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)