Ksecv

ksecv

== 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.

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$. *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.

|
== include(page="template/taskfooter" task_id="ksecv") ==

3245