== include(page="template/taskheader" task_id="ksecv") ==
Se da o secventa $S$ ce contine $N$ numere intregi pozitive. Pozitiile pe care se afla aceste numere sunt numerotate de la $1$ la $N$. O *subsecventa* $S[i:j]$ $(1≤i≤j≤N)$ a unei secvente $S$ este o secventa alcatuita din elementele de pe pozitiile $i$, $i+1$, ..., $j$ din cadrul secventei $S$. Vom spune ca o pozitie $x$ *apartine* unei subsecvente $S[i:j]$, daca $i≤x≤j$.
*Costul* unei subsecvente $S[i:j]$ este egal cu elementul maxim din cadrul acesteia. O *K-impartire* a unei secvente $S$ este o multime de $K$ subsecvente disjuncte (din punct de vedere al pozitiilor din $S$) ale lui $S$, care, impreuna, acopera intreaga secventa $S$ (adica fiecare pozitie din $S$ *apartine* exact unei subsecvente). Costul unei $K-impartiri$ este egal cu suma costurilor celor $K$ subsecvente.
Determinati o $K-impartire$ de cost minim a unei secvente $S$ date.
Poveste si cerinta...
h2. Date de intrare
Prima linie a fisierului de intrare $ksecv.in$ contine doua numere intregi, separate printr-un spatiu: $N$ si $K$. A doua linie contine $N$ numere intregi, reprezentand, in ordine, elementele secventei $S$ date. Doua numere consecutive din cadrul secventei vor fi separate printr-un spatiu.
Fisierul de intrare $ksecv.in$ ...
h2. Date de iesire
In fisierul de iesire $ksecv.out$ veti afisa costul minim al unei $K-impartiri$ a secventei $S$ date in fisierul de intrare.
In fisierul de iesire $ksecv.out$ ...
h2. Restrictii
* $1 ≤ N ≤ 100.000$
* $1 ≤ K ≤ min{N, 100}$
* Orice element al secventei este un numar intreg din intervalul $[0,10.000.000]$.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. ksecv.in |_. ksecv.out |
|7 3
3 2 1 5 6 3 2
|10
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
== include(page="template/taskfooter" task_id="ksecv") ==
h3. Explicatie
...
== include(page="template/taskfooter" task_id="ksecv") ==
