c058: 枯枝 (Branch)
Tags : DP
Accepted rate : 3人/3人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-03 19:17

Content

俗話說「樹大必有枯枝」,園藝用的造景樹可能很大,可能會包含很多枯枝。 如果一棵樹的枯枝程度過高,會影響到整棵樹的美觀,因此我們打算以一棵樹的 「枯枝程度」作為評估美觀程度的依據之一。

園藝用造景樹通常會被修剪成每段樹枝最多只會有 2 個分叉的模樣(即二元 樹),假設已知每段樹枝的枯枝值,則某段樹枝的「子樹枯枝程度」定義為下面 的式子:

子樹枯枝程度 = max(左子樹枯枝程度 , 右子樹枯枝程度 ) + 根樹枝枯枝值 其中若該樹枝的左/右子樹不存在,則其左/右子樹的枯枝程度視為 0。根樹枝的

子樹枯枝程度即為整棵樹的「枯枝程度」。

小懶是個懶惰的園丁,他對於每天反覆計算園藝用造景樹的枯枝程度已經感 到厭煩了,於是他決定將評估枯枝程度的工作委託給其他人來做。即使是委託給 其他人來進行,小懶還是得提供園藝用造景樹的模樣與各段樹枝的枯枝值;但是 小懶實在太懶惰了,所以他想出了一種能夠更加簡化的方法,那就是依照園藝用 造景樹的「前序走訪」記錄各段樹枝的枯枝值,這樣一來就能夠使用一個序列來 同時表示各段樹枝的枯枝值與園藝用造景樹的模樣,小懶對此甚是滿意並開始委 託工作。

圖一:圖中節點內的數值代表各段樹枝的枯枝值,並假設最上方節點為根,其整體枯枝程度為 6,「前序走訪」序列為 [1, 2, 3, 2, 3, 1]。

但此方法存在一個致命性的問題,那就是只記錄園藝用造景樹的「前序走訪」 序列無法還原出唯一園藝用造景樹的模樣,因為可能存在不同模樣的園藝用造景 樹擁有同樣的「前序走訪」序列,所以也就無法正確評估樹的枯枝程度。

  你就是小懶所委託的那個人,請你在只知道依「前序走訪」所記錄各段樹
枝枯枝值序列的情況下,在所有滿足條件的園藝用造景樹之中,評估其整棵樹
枯枝程度的最小值與最大值可能為多少?

 
範例測資
最小與最大 


Input

第一行輸入 1 個正整數 N (1 ≤ N ≤ 1,000),表示園藝用造景樹有 N 段樹枝。 第二行包含 N 個非負整數 di (0 ≤ di ≤ 109) 的序列,表示園藝用造景樹依「前序 走訪」記錄各段樹枝其枯枝值的序列。

Output

為兩個整數值,分別代表對於滿足條件的園藝用造景樹中,其可能的枯枝程 度最小值與最大值。

Sample Input
7 
3 1 1 0 2 0 5
Sample Output
8 12
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
Hint :
Tags:
DP
出處:
TOI線上練習賽 [管理者:
Ching367436 (Ching367436)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」