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

最近更新 : 2018-02-12 15:58

內容

  給定一個長度為N的整數序列a1,a2,...,aN及一個正整數K,請蓋掉任意個數字使得原序列中任意的連續K個數字都至少有一個數字被蓋掉了,請問蓋掉的數字的總和最小為多少?

輸入說明

每筆測資只有一筆輸入

首行有兩個正整數N、K以空格隔開

接下來一行,有N個整數以空格隔開依序代表a1,a2,...,aN

輸出說明

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

範例輸入
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分的測資,N<=20。

對於35分的測資,N<=3000。

對於55分的測資,N<=106

所有測資,K<=N,-109<=ai<=109

標籤:
單調隊列優化
出處:
板橋高中教學題IOICAMP [編輯:
baluteshih (波路特石)
]


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