有一條長長的大街被劃分成 $ n $ 個區段,編號依序為 $ 1$ ~ $n$。在第 $ i $ 個區段設置監控設備的話,需要成本 $ c[i]$ ,而可以監控第 $ i-1 $ 到第 $ i+1 $ 的區段(超出範圍可忽略)。
現在要選一些區段裝設監控設備,以便每一個區段都可以被監控到,請計算最少的總成本。
第一行是正整數 $ n $ 。
第二行有 $ n $ 個非負整數,依序代表第 $ i $ 個區段裝設監控設備的成本,數字間以空白隔開。
$ n ≤ 1e5 $ ,每處成本不超過 $ 1e4 $ 。
最小監控總成本。
5 1 2 3 1 5
2
8 2 1 1 7 3 2 9 2
6
注意當 $n=1$ 時
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |