OpenKattis
POwarmup23 svår: intro DP
Problem D
Köpa tavlor
cc by-s
På marknaden säljs $N$ tavlor längs en lång gata. Tavla $i$ tar $t_ i$ sekunder att köpa. Att gå från en tavla till nästa tar 1 sekund. Mona tar bussen dit och hem, så hon kan välja vid vilken tavla hon börjar och slutar. Vad är den kortaste tiden Mona kan köpa $k$ tavlor på?
Indata
Den första raden innehåller två heltal: $N$ ($1 \le N \le 2000$), antalet tavlor på marknaden, och $k$ ($1 \le k \le N$), antal tavlor Mona behöver köpa.
Den andra raden innehåller $N$ heltal: $1 \le t_1,t_2,...t_ n \le 1000$, antal sekunder det tar att köpa respektive tavla.
Utdata
Skriv ut ett heltal – det minsta antalet sekunder det kan ta för Mona att köpa $k$ tavlor.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Gränser |
|
$1$ |
$7$ |
$k=1$ |
|
$2$ |
$10$ |
$k=2$ |
|
$3$ |
$30$ |
$N \le 200$ |
|
$4$ |
$53$ |
Inga ytterligare begränsningar. |
Exempelfall
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 3 3 5 1 |
6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 4 7 4 3 10 2 5 |
18 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 5 4 7 2 1 8 6 7 2 1 10 |
18 |
