d077: P-6-13. 周伯通的基地台 (@@)
Tags : DP
Accepted rate : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-23 21:33

Content

周伯通開了一家通訊大廠並以他的名字命名,就叫做伯通公司,也有不少人弄錯了稱

為博通。周伯通標下了一個政府標案,要在一條長長的大街架設基地台,長街被劃分

成 n 個區段,編號依序為 1~n。在第 i 個區段架設基地台的話,需要成本 c[i],而

可以服務第 i-k 到第 i+k 的區段(超出範圍可忽略)。現在輸入 k,要選一些區段架

設基地台,以便每一個區段都可以被服務到,請計算最少的總成本。

Input

第一行有兩個正整數 n 與 k。第二行有 n 個正整數,依序代表 c[1],

c[2], …, c[n],數字間以空白隔開。k < n <= 2e5,每處成本不超過 1000。

Output

最小總成本。

Sample Input
// 1
5 1
1 2 3 1 5
// 2
8 2
2 1 1 7 3 2 9 2
Sample Output
// 1
2
// 2
3
測資資訊:
記憶體限制: 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
沒有發現任何「解題報告」