Fişierul intrare/ieşire:ksecv.in, ksecv.outSursăSelectie echipe ACM ICPC, UPB 2008
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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.

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.

Restrictii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ K ≤ min{N, 100}
  • Orice element al secventei este un numar intreg din intervalul [0,10.000.000].

Exemplu

ksecv.inksecv.out
7 3
3 2 1 5 6 3 2
10
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content