h2. 'Polig':problema/polig

La problema polig sunt mai multe solutii, o idee ar fi ca numerele sa fie sortate dupa unghiul cu ox, aceasta era necesara sa se evite un caz particular in solutie. Iar dupa o dinamica $a[i][j]$ = care inseamna maximul astfel incat poligonul sa ajunga pana la segmentul i,j, recurenta iese o({$n$}), in total memorie este o(n^2^) si o(n^3^) complexitate. Mai este o solutie ceva mai faina, dar aceea solutie are copyright Mugurel Ionut Andreica si o las la latitudinea concurentilor, nu necesita cunostinte suplimentare asa ca ar fi interesant ca exercitiu.Hint ca sa nu incercati sa faceti o({$n$}): Complexitatea la solutia lui Mugurel avea sa fie o({$n^2^ lg{~2~}n$}).
 

La problema polig sunt mai multe solutii care se incadreaza in timp pentru limitele date, o idee ar fi ca punctele sa fie sortate dupa unghiul cu axa $Ox$. Apoi, folosind programare dinamica vom construi o matrice cu semnificatia $a[i][j]$ = costul maxim astfel incat sa plecam din orginea planului si sa construim un drum care are ultimele puncte $i$ si $j$. In total, memoria este O(n^2^) si complexitatea in timp O(n^3^). Exista o solutie O({$n^2^ lg{~2~}n$}) data de Mugurel Ionut Andreica, gasirea ei o lasam ca un exercitiu pentru cititori :-). Daca aveti nevoie de ajutor nu ezitati sa folositi forumul.