A在玩跳格子遊戲，遊戲規則如下:
一開始A站在起點上，起點右方的地板上畫有$N$個格子，每個格子內有一個數字(正整數)，A必須從起點開始，不斷的向右跳到某一格內，直到跳到終點(最後一格的右方)，而得分便是他所採到的格子內的數字總和。由於A的跳躍力有限，每一次跳躍只能跳到距離$K$格之內的格子上(也就是假設他現在站在第$i$格，那麼他只能選擇跳到第$i+1,i+2,...,i+K$格)
由於要最大化得分實在太容易了，只要每一格都採就好，因此A想要最小化得分，請問他最少會拿到多少分?
第一行有兩個正整數$N,K$，如題目所述。
第二行有$N$個正整數$a_i$，分別是起點右方第$i$格上所寫的數字。
第一個測資點符合$K=N\le 1000$
第二個測資點符合$K\le N\le 1000$
第三~四個測資點符合$N\le 10^5,K\le min(N,1000)$
第五個測資點符合$K\le N\le 2\times10^5$
所有測資點符合$1\le a_i\le 10^6$
輸出一個正整數代表可能的最小得分。
5 2 3 8 2 1 5
6
範測的跳法是:
起點->第1格(3)->第3格(2)->第4格(1)->終點
因此總和為3+2+1=6分
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||