h2(#peste). 'Peste':problema/peste

 
Sa presupunem ca la momentul $x$ introducem in apa plasa $i$ si vrem in viitor sa introducem si plasa $j$. Avem doua posibilitati: plasa $j$ o introducem la un moment de timp mai mare decat $x+T[i]$ sau la un moment de timp din intervalul $[x,x+T[i]]$. In cazul al doilea cel mai favorabil este sa introducem plasa $j$ la momentul $x$. Odata ce ne hotaram ca la un moment $t$ sa introducem in apa cateva plase este suficient sa fixam timpul maxim de asteptare (momentul la care vom scoate toate plasele introduse la momentul $t$) si sa consideram cel mult $K$ plase care prind cat mai mult peste si timpul in care fac asta este mai mic sau egal decat timpul maxim fixat. Vom preprocesa un vector $aux[t] =$ numarul maxim de pesti pe care ii putem prinde daca plasele introduse au timpul de asteptare mai mic sau egal decat $t$. Apoi, folosind programare dinamica vom calcula vectorul $best[t] =$ numarul maxim de pesti pe care ii putem prinde de la momentul $0$ la momentul $t$. Solutia se va afla in $best[T]$. Relatia de recurenta va fi $best[t] = max(best[t-1]+aux[ 1 ], best[t-2]+aux[ 2 ]...best[t-TMAX]+aux[TMAX])$. Complexitatea solutiei va fi $O(N*logK+T*TMAX)$, unde $TMAX$ este timpul maxim de asteptare a unei plase (in cazul nostru $1000$). Pentru a preprocesa vectorul $aux[]$ putem folosi un heap sa obtinem complexitatea acestui pas $O(N*logK)$.