c528.
相隔小於一定距離最小總和子序列
內容
給定一個長度為$\color{black}{\space N \space}$的整數序列$\color{black}{\space a_1,a_2,\dots,a_N \space}$及一個正整數$\color{black}{\space K \space}$，請蓋掉任意個數字使得原序列中任意的連續$\color{black}{\space K \space}$個數字都至少有一個數字被蓋掉了，請問蓋掉的數字的總和最小為多少？
輸入說明
每筆測資只有一筆輸入
首行有兩個正整數$\color{black}{\space N,K \space}$以空格隔開
接下來一行，有$\color{black}{\space N \space}$個整數以空格隔開依序代表$\color{black}{\space a_1,a_2,\dots,a_N \space}$。
輸出說明
輸出蓋掉的數字之最小總和於一行。
範例輸入
#1
5 2 8 3 6 5 7
範例輸出
#1
8
測資資訊：
記憶體限制：
512
MB
不公開 測資點#0 (4%): 1.0s , <1K
不公開 測資點#1 (3%): 1.0s , <1K
不公開 測資點#2 (3%): 1.0s , <1K
不公開 測資點#3 (9%): 1.0s , <1M
不公開 測資點#4 (9%): 1.0s , <1M
不公開 測資點#5 (9%): 1.0s , <1M
不公開 測資點#6 (8%): 1.0s , <1M
不公開 測資點#7 (14%): 1.0s , <10M
不公開 測資點#8 (14%): 1.0s , <10M
不公開 測資點#9 (14%): 1.0s , <10M
不公開 測資點#10 (13%): 1.0s , <10M
不公開 測資點#0 (4%): 1.0s , <1K
不公開 測資點#1 (3%): 1.0s , <1K
不公開 測資點#2 (3%): 1.0s , <1K
不公開 測資點#3 (9%): 1.0s , <1M
不公開 測資點#4 (9%): 1.0s , <1M
不公開 測資點#5 (9%): 1.0s , <1M
不公開 測資點#6 (8%): 1.0s , <1M
不公開 測資點#7 (14%): 1.0s , <10M
不公開 測資點#8 (14%): 1.0s , <10M
不公開 測資點#9 (14%): 1.0s , <10M
不公開 測資點#10 (13%): 1.0s , <10M
提示 ：
對於10分的測資，$\color{black}{\space N\leq 20 \space}$。
對於35分的測資，$\color{black}{\space N\leq 3000 \space}$。
對於55分的測資，$\color{black}{\space N\leq 10^6 \space}$。
所有測資，$\color{black}{\space K\leq N \space}$，$\color{black}{\space -10^9 \leq a_i \leq 10^9\space}$。
標籤:
出處:
板橋高中教學題IOICAMP
[管理者：
baluteshih
(波路特石)
]