Revizia anterioară Revizia următoare
Cea mai importanta observatie ce ajuta la rezolvarea acestei probleme este ca avand i drepte deja desenate si adaugand o dreapta noua neparalela cu nici una din cele i dinainte se vor forma i intersectii noi si i + 1 zone noi in care este impartita foaia. In continuare daca avem i drepte deja desenate si adaugam k drepte noi paralele intre ele dar neparalele cu nici una din cele i drepte deja desenate se vor forma i * k intersectii noi, si (i + 1) * k zone noi in care este impartita foaia. 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 N3.
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)
