h2. 'Polig':problema/polig

Exista 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.

Exista 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)$ propusa de Mugurel Ionut Andreica, gasirea ei o lasam ca un exercitiu pentru cititori :-). Daca aveti nevoie de ajutor nu ezitati sa folositi forumul.