008 Subsir crescator maximal

[•wefgef]

Numarul de solutii creste exponential.

[•darkseeker]

Daca vrei sa le afisezi pe toate atunci cand actualizezi valoarea dp[ i ] ,tii o lista cu toate valorile din care poti obtine valoarea maxima pentru dp[ i ] . Iti dau un exemplu , pentru a fi mai clar :
sa zicem ca ai sirul 2 10 15 3 11 16. In acest sir elementele au urmatorii precedenti :
2 -> nu e precedat de nimeni
10-> e precedat de 2
15 -> e precedat de 10
3-> 3 precedat de 2
11 -> e precedat atat de 3 cat si 10 ambele valori ducand la un subsir de lungime 3
16-> e precedat de 11,3,15 toate 3 ducand la un subsir de lungime 4
Acum pentru a genera toate subsirurile maximale algoritmul este urmatorul :
Iei fiecare precedent al unui element pentru care dp[ i ] = 4, pentru fiecare precedent iei fiecare precedent al acestuia si tot asa ... pana ajungi la un element ce nu e precedat de nimic .
Poate nu am fost suficient de clar , nu sunt tocmai un as al explicatiilor , dar daca mai ai nelamuriri dam un pm si vad cum te pot ajuta , eventual iti dau o sursa sa vezi cum se face .

[•andunhill]

Cred ca trebuie marita putin limita de timp. Am implementat o solutie cu normalizare( cu lower_bound) + AIB + parsare si iau tle pe testul 9.

[•alex_unix]

Am incercat sa implementez cu AIB si iau TLE pe testul 9. Nici sursa data ca model nu e de 100, tot din cauza testului 9, desi in josul paginii scrie ca obtine 100  .
Modelul : http://infoarena.ro/job_detail/809153
A mea : http://infoarena.ro/job_detail/809148

[•bratiefanut]

am facut un algoritm cu programare dinamica, complexitatea fiind O(N²). merge dar pe ultimele 3 teste imi da TLE. aveti vreo idee despre cum as putea modifica algoritmul in asa fel incat sa fie mai rapid?

[•PlayLikeNeverB4]

Trebuie sa scoti complexitate mai buna. Citeste indicatiile de rezolvare.

[•bratiefanut]

In sfarsit am luat 100 multumesc

[•costyv87]

Solutia cu AIB-uri nu intra in timp (nici macar solutia oficiala) . Nu stiu daca s-a mai zis , dar m-am gandit ca e ok sa stiti.

[•witsel]

ce inseamna erorile: killed by signal 6 si lungime incorecta. Daca s-ar putea uita cineva pe sursele mele as fi recunoscator:D

[•BlueCode]

imi poate spune cineva de ce imi apare subsir incorect?

[•nicolaefilat]

      Sunt nou pe infoarena si as vrea sa inteleg de ce sursa me primeste doar 10 puncte , am facut mai mult teste pe ea si toate mergeau (ex:  5 54321 : 1 1 ; 5  2412151519 : 3 12 15 19  ..etc).

Plz ajutati-ma !

aici e linkul : http://www.infoarena.ro/job_detail/1971925?action=view-source

Mersi