antivirus

Antivirus

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

Poveste şi cerinţă...

Se consideră un șir de $N$ numere naturale. O parte dintre poziţiile șirului sunt nevirusate și acest lucru este marcat prin faptul că valoarea de la acele poziţii este $0$. Restul poziţiilor sunt virusate și valoarea nenulă de la o poziţie virusată reprezintă costul cu care ea poate fi devirusată. Devirusăm o parte dintre poziţii și dorim ca în final să avem exact $K$ poziţii nevirusate, iar costul total al devirusării să fie minim. O poziţie poate fi devirusată la un moment dat, dacă și numai dacă are cel puţin o poziţie vecină nevirusată. După devirusarea unei poziţii costul asociat acesteia se adună la costul total, poziţia devine nevirusată si orice altă poziţie vecină virusată va putea fi ulterior devirusată.
 
h2. Cerință
 
Cunoscând $N, K$ și șirul de numere naturale să se determine costul minim cu care se pot obţine la final exact $K$ poziţii nevirusate (incluzând şi poziţiile ce au fost iniţial nevirusate).

h2. Date de intrare

Fişierul de intrare $antivirus.in$ ...

Fișierul de intrare $antivirus.in$ va conține pe prima linie numărul natural $T$ – numărul de teste. Fiecare test este descris pe două linii. Pe prima linie se găsesc două numere naturale $N$ și $K$ cu semnificația din enunţ si pe a doua linie $N$ numere naturale reprezentând elementele șirului.

h2. Date de ieşire

h2. Date de ieșire

În fişierul de ieşire $antivirus.out$ ...

Fișierul de ieșire antivirus.out trebuie să conțină $T$ linii. Pe fiecare linie va fi afișat răspunsul pentru un test - un număr natural reprezentând costul minim al unei devirusări astfel încât în final șirul să conțină exact K poziții nevirusate – inclusiv cele care erau inițial nevirusate.

h2. Restricţii

h2. Restricții și precizări

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 4$
* $1 ≤ K ≤ N ≤ 2000$
* $0 ≤ a[i] ≤ 1000000$
* $1 ≤$ numarul de $0$-uri din sir $≤ K$
* pentru teste în valoare de $10$ puncte se garantează că $N ≤80$
* pentru alte teste în valoare de $20$ puncte se garantează că $N ≤200$
* pentru alte teste în valoare de $10$ puncte în şirul iniţial există exact o poziție nevirusată
* pentru alte teste în valoare de $10$ puncte în şirul iniţial există exact $2$ poziții nevirusate

h2. Exemplu
table(example). |_. antivirus.in |_. antivirus.out |

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

| 2
8 5
9 1 4 4 0 1 3 9
6 4
1 0 2 0 1 1
| 10
2

|

h3. Explicaţie
 
...
 

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