h3. (clasele 11-12)

Problema se poate rezolva folosind metoda programarii dinamice. Se construieste matricea $A{~t,i~}$ in care se retine valoarea totala a amenzilor ce poate fi data pana la momentul $t$ astfel incat la momentul $t$ sa fim in intersectia {$i$}. Pentru toate muchiile ({$j,i$}) de cost $c$ vom compara {$A{~t,i~}$} cu {$A{~t-c,j~}$} alegand maximul dintre aceste valori. De fapt ar trebui inspectate toate valorile {$A{~t-c,j~}$} {$A{~t-c-1,j~}$} ... {$A{~1,j~}$} {$A{~0,j~}$} dar este clar ca maximul acestor valori se afla in {$A{~t-c,j~}$}. Deasemenea trebuie considerat cazul cand politistul sta pe loc deci ne vom uita si la valoarea din {$A{~t-1,i~}$}. Apoi politistul va da toate amenzile posibile la momentul respectiv in intersectia respectiva deci vom aduna respectiva suma la {$A{~t,i~}$}.
Avand construita aceasta matrice se poate raspunde in $O(1)$ la fiecare intrebare.
Complexitatea totala va fi $O(Tmax * M)$ ca timp si $O( Tmax * N )$ ca memorie.

...

h2. Secventa 5