c528: 相隔小於一定距離最小總和子序列
標籤 : 單調隊列優化
通過比率 : 83% (15 人 / 18 人 ) (非即時)
評分方式:
Strictly

最近更新 : 2018-07-02 19:41

內容

  給定一個長度為$\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}$。

輸出說明

輸出蓋掉的數字之最小總和於一行。

範例輸入
5 2
8 3 6 5 7
範例輸出
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
提示 :

對於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 (波路特石)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」