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).
