Cost mínim de parentitzar correctament (1) P76915


Statement
 

pdf   zip

html

Donada una paraula composta només per parèntesis que obren i tanquen, cal convertir-la en una parentització correcta. L’única operació que es pot fer és girar cada parèntesi, és a dir, canviar la seva orientació. Quin és el mínim nombre de girs necessari?

Per exemple, si la paraula és “)(()((()”, llavors es pot aconseguir la parentització correcta “((())())” girant només tres parèntesis, i no es pot fer amb cost inferior.

Entrada

L’entrada consisteix en diversos casos, cadascun amb una paraula amb n parèntesis que obren o tanquen. Podeu suposar que n és parell i que està entre 2 i 100.

Sortida

Per a cada cas, escriviu el cost mínim de parentitzar correctament.

Pista

Encara que hi ha solucions més eficients, és suficient una programació dinàmica de cost temporal Θ(n3 ) i cost espacial Θ(n2 ).

Public test cases
  • Input

    ()
    ()()
    (()(
    ))))
    ))((
    )(
    )(()((()
    

    Output

    0
    0
    1
    2
    2
    2
    3
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++