o problemuta...

[•Andreid91]

Am si eu o mica probemuta la care ma chinui de ceva zile incoace.... Daca e cineva binevoitor sa-si arunce privirea peste ea....

Deci, problema suna ceva de genu:
 
"Se da o expresie formata dintr-un sir de max. 100 numere reale intre care avem semnele + sau *.Puneti paranteze in acest sir astfel ca rezultatul operatiilor sa fie maxim.Fisierul de intrare maxim.in contine o singura linie cu expresia dataFisierul de iesire maxim.out va contine expresia cu paranteze

Exemplu:

maxim.in
 -3*0.1+4*0.2*-2+4

maxim.out
-3*(0.1+4*0.2)*-2+4

Restrictii:

Sunt cel mult 100 de numere in expresia data
Numerele sunt din intervalul [-100, 100] si au cel mult doua zecimale"

 

[•wefgef]

Solutia evidenta este programare dinamica in O(N^3). Construiesti o matrice A[ i ][ j ] - valoarea maxima ce se poate obtine daca folosim teremenii cu indicii i, i+1, ..., j.

Ma intreb daca merge vre-un greedy la problema asta

[•Andreid91]

mersi wef