Inverseaza reviziile

Diferente pentru problema/ksecv intre reviziile #1 si #7

Diferente intre titluri:

ksecv

Ksecv

Diferente intre continut:

== include(page="template/taskheader" task_id="ksecv") ==

Poveste si cerinta...

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.

h2. Date de intrare

Fisierul de intrare $ksecv.in$ ...

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.

h2. Date de iesire

In fisierul de iesire $ksecv.out$ ...

In fisierul de iesire $ksecv.out$ veti afisa costul minim al unei $K-impartiri$ a secventei $S$ date in fisierul de intrare.

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 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|7 3
3 2 1 5 6 3 2
|10

|

h3. Explicatie
 
...
 

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

Nu exista diferente intre securitate.

Diferente intre topic forum:

 

3245