主題

ZeroJudge - f817: TOI_y21m4_a03枯枝 解題心得

Not In My Back Yard | 2021-05-22 00:00:08 | 巴幣 0 | 人氣 63

題目連結:


題目大意:
輸入第一列給定一正整數 N (1 ≦ N ≦ 1000),代表有一棵樹有 N 枝樹枝(可以視為圖論中圖的「節點」),每枝樹枝有一個「枯枝值」。接著的第二列給定 N 個非負整數,代表這棵樹根據前序探訪(Preorder Traversal,這題有介紹)後所產生的枯枝值序列。

此時,我們定義整棵樹的枯枝程度為
max(左子樹枯枝程度, 右子樹枯枝程度) + 根節點(樹枝)枯枝值
其中,如果有樹枝沒有左子樹或是右子樹則將對應的枯枝程度之值視為 0 。

試問根據給定前序探訪之枯枝值序列,在所有我們可以還原出的樹中,最小以及最大的枯枝程度之值為何?



範例輸入:
範例輸入 #1
3
1 2 0

範例輸入 #2
7
3 1 1 0 2 0 5

範例輸入 #3
10
1 2 3 0 2 3 3 0 2 5


範例輸出:
範例輸出 #1
3 3

範例輸出 #2
8 12

範例輸出 #3
6 21


解題思維:
可以看到,當所有樹枝只有左子樹或是右子樹時,根樹枝的枯枝程度即是全部樹枝的枯枝值之總和。因此枯枝值總和即是最大的枯枝程度。

而我們定義 D[i][j] 為序列中第 i ~ 第 j 個樹枝(方便起見,這邊統一 i < j,且索引值從 0 開始)所能形成的最小枯枝程度,則我們可以看到
當 i = j 時,D[i][j] = 第 i 根樹枝的枯枝值;
當 i = j - 1 時,D[i][j] = 第 i 根以及第 j 根樹枝的枯枝值總和;
除上之外的情況為,D[i][j] = D[i][i] + min(max(D[i+1][k], D[k+1][j]),i+1 ≦ k < j)

可以看到上面的第三種情況有點類似於最佳矩陣相乘,例如這題。因此作法可以參見該題的求法,一步步求出各個數對 (i, j) 的 D[i][j] 值。

而所求的最小枯枝程度即是 D[0][N - 1]。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作