Pagini recente » Diferente pentru problema/valutar intre reviziile 6 si 7 | Autentificare | Istoria paginii utilizator/camic | Harta3 | Diferente pentru problema/paznici3 intre reviziile 4 si 9
Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="paznici3") ==
Se da un arbore cu $N$ noduri si $M$ paznici. Pentru a angaja paznicul $i$ trebuie sa platesti costul $Z{~i~}$. Se stie ca daca angajezi paznicul $i$, atunci acesta va pazi tot lantul din arbore de la nodul $A{~i~}$ pana la nodul $B{~i~}$. Se cere sa se determine costul minim pentru a pazi tot arborele. Un nod nu are voie sa fie pazit de mai mult de un paznic.
Se da un arbore cu $N$ noduri si $M$ paznici. Pentru a angaja paznicul $i$ trebuie sa platesti costul $Z{~i~}$. Se stie ca daca angajezi paznicul $i$, atunci acesta va pazi toate nodurile de pe lantul de la nodul $A{~i~}$ pana la nodul $B{~i~}$. Se cere sa se determine costul minim pentru a pazi tot arborele. Un nod nu are voie sa fie pazit de mai mult de un paznic.
h2. Date de intrare
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 200.000$
* valorile elementelor sunt pana in $10.000$
* se garanteaza ca exista solutie
h2. Exemplu
| 23
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="paznici3") ==
Nu exista diferente intre securitate.
Diferente intre topic forum:
