723 Stiva

[•DITzoneC]

Aici puteţi discuta despre problema Stiva.

[•Florian]

Iau TLE cu o dinamica in O(N^3) . Se poate mai rapid? 

[•gabitzish1]

Mi se pare ca solutia oficiala e tot n^3.

[•Florian]

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 ?

[•S7012MY]

E prea mica limita de timp

[•wefgef]

Am modificat-o la 0.2

[•mvcl3]

Explicati-mi si mie un pic va rog ideea cu o(n^3) ca nu ma prind 

[•vendetta]

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];
sau dp[i][j] = dp[i][k] + dp[k+1][j-1], cu k = i,j-1 si Text[k] == Text[j];// asta inseamna ca fac sirul i...k cu un numar minim de operatii dupa care il fac pe k+1...j-1 si cand il pun pe j nu il pun in mod practic ( adica numai apelez push() ) ci scot tot ce e pe 
intervalul [k+1..j-1] si o sa ii dau "top()" de Text[j];

[•mvcl3]

Multumesc frumos! am luat 100p