俗話說「樹大必有枯枝」,園藝用的造景樹可能很大,可能會包含很多枯枝。 如果一棵樹的枯枝程度過高,會影響到整棵樹的美觀,因此我們打算以一棵樹的 「枯枝程度」作為評估美觀程度的依據之一。
園藝用造景樹通常會被修剪成每段樹枝最多只會有 2 個分叉的模樣(即二元 樹),假設已知每段樹枝的枯枝值,則某段樹枝的「子樹枯枝程度」定義為下面 的式子:
子樹枯枝程度 = max(左子樹枯枝程度 , 右子樹枯枝程度 ) + 根樹枝枯枝值 其中若該樹枝的左/右子樹不存在,則其左/右子樹的枯枝程度視為 0。根樹枝的
子樹枯枝程度即為整棵樹的「枯枝程度」。
小懶是個懶惰的園丁,他對於每天反覆計算園藝用造景樹的枯枝程度已經感 到厭煩了,於是他決定將評估枯枝程度的工作委託給其他人來做。即使是委託給 其他人來進行,小懶還是得提供園藝用造景樹的模樣與各段樹枝的枯枝值;但是 小懶實在太懶惰了,所以他想出了一種能夠更加簡化的方法,那就是依照園藝用 造景樹的「前序走訪」記錄各段樹枝的枯枝值,這樣一來就能夠使用一個序列來 同時表示各段樹枝的枯枝值與園藝用造景樹的模樣,小懶對此甚是滿意並開始委 託工作。
圖一:圖中節點內的數值代表各段樹枝的枯枝值,並假設最上方節點為根,其整體枯枝程度為 6,「前序走訪」序列為 [1, 2, 3, 2, 3, 1]。
但此方法存在一個致命性的問題,那就是只記錄園藝用造景樹的「前序走訪」 序列無法還原出唯一園藝用造景樹的模樣,因為可能存在不同模樣的園藝用造景 樹擁有同樣的「前序走訪」序列,所以也就無法正確評估樹的枯枝程度。
你就是小懶所委託的那個人,請你在只知道依「前序走訪」所記錄各段樹 枝枯枝值序列的情況下,在所有滿足條件的園藝用造景樹之中,評估其整棵樹 枯枝程度的最小值與最大值可能為多少?
第一行輸入 1 個正整數 N (1 ≤ N ≤ 1,000),表示園藝用造景樹有 N 段樹枝。
第二行包含 N 個非負整數 di (0 ≤ di ≤ 109) 的序列,表示園藝用造景樹依「前序 走訪」記錄各段樹枝其枯枝值的序列。
為兩個整數值,分別代表對於滿足條件的園藝用造景樹中,其可能的枯枝程 度最小值與最大值。
7 3 1 1 0 2 0 5
8 12
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |