修補圍籬 (APCS 2021-11 初級)

有一個農場有寬度為 \(n\) 的圍籬，每片圍籬都有各自的高度 \(h[1], h[2], \ldots, h[n]\)。

有些圍籬被吹斷了（高度為 \(0\)），農場主人要來修補這些圍籬，但他忘記這些壞掉的圍籬原本高度是多少。為了減少成本，他會取斷掉圍籬位置相鄰左、右兩側中較小的那個高度填上去；請問需要多少成本（新增的圍籬高度總和）。

題目保證不會有兩片相鄰的圍籬同時被吹斷，而被吹斷的圍籬有可能位在邊界（此時只有一側有鄰居，就取該側的高度）。

輸入格式

輸入包含兩行：

• 第一行有一個正整數 \(n\)。
• 第二行有 \(n\) 個以空白分隔的整數 \(h[1], h[2], \ldots, h[n]\)。

限制

• \(3 \le n \le 100\)
• \(0 \le h[i] \le 100\)
• 不會有兩片相鄰的圍籬同時被吹斷（同時為 \(0\)）

輸出格式

輸出一個整數，表示新增的圍籬高度總和。

評分說明

每一筆測試資料的執行時間限制均為 \(1\) 秒，依正確通過的測試資料筆數給分。其中：

• 第 1 子題組（\(60\) 分）：\(n = 3\)。
• 第 2 子題組（\(40\) 分）：無額外限制。

範例輸入 1

3
2 0 4

範例輸出 1

2

（說明）中間的圍籬被吹斷，取左右較小者 \(\min(2, 4) = 2\)。

範例輸入 2

9
0 5 3 0 6 4 0 1 0

範例輸出 2

10

（說明）位置 \(1\)（左邊界）填 \(5\)、位置 \(4\) 填 \(\min(3, 6) = 3\)、位置 \(7\) 填 \(\min(4, 1) = 1\)、位置 \(9\)（右邊界）填 \(1\)，總和 \(5 + 3 + 1 + 1 = 10\)。

題目來源

APCS 2021 年 11 月實作題第 1 題。

• ZeroJudge g595