|
Titlul: 723 Stiva Scris de: Adrian Diaconu din Mai 24, 2008, 12:43:49 Aici puteţi discuta despre problema Stiva (http://infoarena.ro/problema/stiva).
Titlul: Răspuns: 723 Stiva Scris de: Florian Marcu din Octombrie 15, 2009, 17:12:17 Iau TLE cu o dinamica in O(N^3) . Se poate mai rapid? :-k
Titlul: Răspuns: 723 Stiva Scris de: Gabriel Bitis din Octombrie 15, 2009, 17:27:12 Mi se pare ca solutia oficiala e tot n^3.
Titlul: Răspuns: 723 Stiva Scris de: Florian Marcu din Octombrie 15, 2009, 17:33:42 Mda. Am trimis si sursa oficiala, care e o(n^3), si ia tot 80 de puncte. Care e optimizarea ce trebuie facuta pt 100 ?
Titlul: Răspuns: 723 Stiva Scris de: Petru Trimbitas din Septembrie 26, 2012, 17:36:17 E prea mica limita de timp
Titlul: Răspuns: 723 Stiva Scris de: Andrei Grigorean din Octombrie 01, 2012, 19:29:50 Am modificat-o la 0.2
Titlul: Răspuns: 723 Stiva Scris de: Marian Iacob din Iunie 25, 2013, 18:30:19 Explicati-mi si mie un pic va rog ideea cu o(n^3) ca nu ma prind ](*,)
Titlul: Răspuns: 723 Stiva Scris de: Salajan Razvan din Iunie 25, 2013, 20:58:53 Ideea se bazeaza pe o dinamica in n^3. In primul rand pentru orice sir vei folosi n operatii de tipul top(); numarul de operatii de tipul push() va fi tot timpul egal cu numarul de operatii de tipul pop(). Acum problema devine in afla numarul minim de operatii de tipul push() a. i. sa obtii sirul [i..j]; Raspunsul final fiind Nr minim de operatii de a obtine sirul 1...n * 2 (nr de pop-uri) + n (nr de top() -uri); dinamica ar fi dp[ i ] [ j ] = nr minim de operatii de tipul push pentru a obtine sirul i...j;
Cod: dp[i][j] = dp[i][j-1] + 1;// pur si simplu mai pun caracaterul Text[j]; Titlul: Răspuns: 723 Stiva Scris de: Marian Iacob din Iunie 26, 2013, 15:42:02 Multumesc frumos! am luat 100p :banana:
|