preoni-2008/runda-4/solutii/carnati

Solutie

h2(#carnati). 'Carnati':problema/carnati

 
Prima observatie pe care o facem este faptul ca pretul fixat de Gigel va fi unul dintre preturile clientilor sai. Odata ce avem fixat un pret {$X$} putem sa construim o dinamica {$A{~i~}$} profitul maxim daca magazinul este deschis in momentul in care trece clinetul {$i$} (clientii vor fi sortati crescator dupa timpul la care trec). Relatia de recurenta se observa usor {$A{~i~}= max(A{~i-1~}-(T{~i~}-T{~i-1~})*C+G,G-C$}), unde {$G$} este {$X$} pentru {$X ≤ P{~i~}$} sau {$0$} in caz contrar. De fapt, avand fixat {$X$} si construind vectorul {$H{~2*i~}=G-C$}, {$H{~2*i+1~}={@-@}(T{~i~}-T{~i-1~})*C$} problema se reduce la determinarea subsecventei de suma maxima.
 
Complexitatea de rezolvare pentru {$X$} fixat este {$O(N)$}, deci in final algoritumul va fi {$O(N^2^)$}