In urma fiecarui set de cate 4 operatii, putem desena in plan valorile din dp[] sub forma unui grafic cu puncte (j, dp[j]). Acest grafic are forma unui sir de segmente cu pante crescatoare, primul segment avand panta negativa, iar ultimul segment avand panta egala cu lambda. E suficient sa retinem, intr-o structura de date, capetele de imbinare ale segmentelor, respectiv cu cat se schimba panta la fiecare imbinare. Desigur, pentru a calcula raspunsul, care este o pereche <cost_total, cnt_operatii_de_tip_2>, vom avea nevoie sa retinem si cateva informatii legate de:
- cate operatii de tipul 2 au fost facute pentru determinarea valorii lui dp0
- care este prima valoare din dp
- care este valoarea primei derivate
Cum se modifica structura aceasta (de preferat sa ganditi pe grafic) la fiecare tip de operatie si cum putem manipula operatiile cat mai eficient? Cum ne putem asigura ca minimizam (sau maximizam) valoarea lui cnt?
