639 Zmeu

[•DITzoneC]

Aici puteţi discuta despre problema Zmeu.

[•Dorin_]

cum adica "pericolul se conserva" ? eventual se aduna

[•cos_min]

Sa zicem ca suntem in punctul P cu pericolul K, atunci ca sa ajungi intr-o pozitie noua se mentine/conserva acelasi pericolul K la care se adauga daca este necesar pericolul din pozitia noua.

[•wefgef]

Presupun ca solutia oficiala are complexitatea O(N^2 * P). Cred ca puteai sa dai P-ul ala mult mai mare si sa faci un Bellman-Ford. Ar fi crescut dificultatea problemei destul de mult.

[•lucian666]

  Salut . Care este traseul parcurs pt a obtine costul 2 ? 

[•ctlin04]

Sunt doua modalitati de a ajunge cu costul 2:
1. 1,1->1,2->2,2->3,2->4,2->4,3->4,4;
2. 1,1->2,1->2,2->3,2->4,2->4,3->4,4;
In ambele cazuri vei plati 1 pentru a anula pozitia 2,2 si inca 1 pentru a anula pozitia 4,2 si astfel in primul caz ajungi cu un pericol conservat de 6 unitati, iar in cazul doi pericolul v-a fi de 5 unitati, respectiv ambele<=6 

[•array]

Presupun ca solutia oficiala are complexitatea O(N^2 * P). Cred ca puteai sa dai P-ul ala mult mai mare si sa faci un Bellman-Ford. Ar fi crescut dificultatea problemei destul de mult.

Am rezolvat problema asta in O (N ^ 2 * P) , dar nu-mi dau seama cum s-o fac pentru un P mai mare cu Bellman-Ford. Am cautat sa vad si la celelalte surse, dar vad ca toate care au luat 100p au tot N ^ 2 * P. Imi poate explica va rog cineva mai in amanunt ideea sugerata de wefgef?