==include(page="nave-lucian-hint4")==

---

==include(page="nave-lucian-hint5")==
---

!nave-prea-usor?Type1.jpg!
 
In imaginea de mai sus puteti vedea cum se schimba graficul in timpul operatiei de tip $1$. Practic, segmentul care intersecteaza pozitia $0$ este sectionat, intrucat trebuie sa notam ca acolo este o dubla schimbare de panta.
 
!nave-prea-usor?Type2.jpg!
 
In aceasta imagine puteti vedea cum se schimba graficul in timpul operatiei de tip $2$. Tot ce se intampla e ca in dreptul minimului este inserat un segment de lungime $1$ si panta $0$, partea din dreapta a graficului "mutandu-se" cu o pozitie mai la dreapta, iar cea din stanga ramanand intacta. De asemenea, de retinut ca toate valorile din dreapta minimului nu doar ca si-au schimbat, prin aceasta operatie, valoarea din $dp[]$, ci chiar si acea valoare $cnt$ (care ne spune cate unitati de flux merg direct la Destinatie) este incrementata!
 
Operatia de tip $3$ inseamna sa scadem panta ultimului segment, iar operatia $4$ este o simpla shiftare a graficului cu $input[i+1]$ pozitii.
 
 

==include(page="nave-lucian-hint6")==

 
Bucla critica (cea care da complexitatea) este data de numarul de pasi pe care ii fac ce doi iteratori:
 
* $(1)$
 
*In concluzie*, am putea rezuma solutia aceasta ca: smenul de la Aliens + optimizare de dinamica cu slope trick / mentinerea celei de-a doua derivate discrete + liste dublu inlantuite.