2504 問題 E: 信息學奧賽一本通T1602-烽火傳遞
時間限制: 1s
內(nèi)存限制: 128MB 提交: 51 解決: 30
題目描述
原題來自：NOIP 2010 提高組初賽 · 完善程序
烽火臺是重要的軍事防御設(shè)施，一般建在交通要道或險要處。一旦有軍情發(fā)生，則白天用濃煙，晚上有火光傳遞軍情。
在某兩個城市之間有 n 座烽火臺，每個烽火臺發(fā)出信號都有一定的代價。為了使情報準確傳遞，在連續(xù) m 個烽火臺中至少要有一個發(fā)出信號?，F(xiàn)在輸入 n,m 和每個烽火臺的代價，請計算總共最少的代價在兩城市之間來準確傳遞情報。
輸入
第一行是 n,m，表示 n 個烽火臺和連續(xù)烽火臺數(shù) m；
第二行 n 個整數(shù)表示每個烽火臺的代價 ai 。
提示
樣例說明
在第 2,5 號烽火臺上發(fā)信號。
數(shù)據(jù)范圍與提示：
對于全部數(shù)據(jù)，1≤n,m≤2×105,1≤ai≤1000。