d068: P-6-3. 最小監控鄰居的成本
Tags : DP
Accepted rate : 70人/137人 ( 51% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-03-28 14:58

Content

有一條長長的大街被劃分成 $ n $ 個區段,編號依序為 $ 1$ ~ $n$。在第 $ i $ 個區段設置監控設備的話,需要成本 $ c[i]$ ,而可以監控第 $ i-1 $ 到第 $ i+1 $ 的區段(超出範圍可忽略)。

現在要選一些區段裝設監控設備,以便每一個區段都可以被監控到,請計算最少的總成本。

Input

第一行是正整數 $ n $ 。

第二行有 $ n $ 個非負整數,依序代表第 $ i $ 個區段裝設監控設備的成本,數字間以空白隔開。

$ n ≤ 1e5 $ ,每處成本不超過 $ 1e4 $ 。

Output

最小監控總成本。

Sample Input #1
5
1 2 3 1 5
Sample Output #1
2
Sample Input #2
8
2 1 1 7 3 2 9 2
Sample Output #2
6
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (6%): 1.0s , <1K
公開 測資點#1 (6%): 1.0s , <1K
公開 測資點#2 (6%): 1.0s , <1K
公開 測資點#3 (6%): 1.0s , <1M
公開 測資點#4 (6%): 1.0s , <1M
公開 測資點#5 (7%): 1.0s , <1M
公開 測資點#6 (7%): 1.0s , <1M
公開 測資點#7 (7%): 1.0s , <1M
公開 測資點#8 (7%): 1.0s , <1M
公開 測資點#9 (7%): 1.0s , <1M
公開 測資點#10 (7%): 1.0s , <1M
公開 測資點#11 (7%): 1.0s , <1M
公開 測資點#12 (7%): 1.0s , <1M
公開 測資點#13 (7%): 1.0s , <1M
公開 測資點#14 (7%): 1.0s , <1M
Hint :

注意當 $n=1$ 時

Tags:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


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