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

最近更新 : 2020-11-18 19:42

Content

有一條長長的大街被劃分成 n 個區段,編號依序為 1~n。在第 i 個區段設置監控設

備的話,需要成本 c[i],而可以監控第 i-1 到第 i+1 的區段(超出範圍可忽略)。

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

成本。

Input

第一行是正整數 n。第二行有 n 個非負整數,依序代表第 i 個區段裝設監

控設備的成本,數字間以空白隔開。n ≤ 1e5,每處成本不超過 1e4。

Output

最小監控總成本。

Sample Input
//case 1
5
1 2 3 1 5
//case 2
8
2 1 1 7 3 2 9 2
Sample Output
//case 1
2
//case 2
6
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :
Tags:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


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