Revizia anterioară Revizia următoare
Asadar problema se poate rezolva prin progamare dinamica. Fie din[i][j] numarul maxim de zone in care poate fi impartita foaia astfel incat sa fi desenat i drepte ce se intersecteaza in j puncte, sau 0 in caz ca i drepte nu pot forma j intersectii. Valoarea initiala a aceste dinamici va fi din[ 0 ][ 0 ] = 1 . Vom porni de la dimensiunile mai mici ale dinamicii (adica vom parcurge starile dinamicii in ordine crescatoare dupa i si apoi j). Daca suntem in starea din[i][j] != 0 , vom incerca sa desenam k noi drepte paralele intre ele dar neparalele cu nici una din cele i deja desenate si vom actualiza din[i + k][j + (i * k)] = max(din[i + k][j + (i * k)], din[i][j] + (i + 1) * k) .
O alta observatie utila ar fi ca numarul maxim de zone in care poate fi impartit planul de i drepte ce formeaza j intersectii este unic determinat de i si j si este egal cu i + j + 1 . Ajutandu-ne de aceasta observatie trebuie doar sa stim daca i drepte pot forma j intersectii si putem schimba dinamica in din[i][j] este 1 sau 0 daca i drepte se pot intersecta in j puncte, si astfel putem reduce memoria folosind stari pe biti. Acest lucru nu era necesar pentru a obtine punctaj maxim.
Solutia aceasta are complexitatea N^3 .
Soluţie alternativă
Având în vedere că numărul maxim de zone în care poate fi împărţit planul de i drepte ce formează j intersecţii este unic determinat, pentru a afla o anumită configuraţie (i, j) este necesar să calculăm maxim i configuraţii. Astfel, vom calcula doar configuraţiile necesare, folosind memoizarea. Această soluţie are complexitatea O(T*N)
