ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1183. Brackets Sequence

some hints
Posted by hliu20 18 May 2013 15:26
1. DP,  f[i][j] represents when solving the substring from index i to j the minimum brackets should add. Then we have
    1) i <= j
    2) if i == j, then f[i][j] = 1. (you can add a bracket to match the one)
    3) if i < j, then f[i][j] = min(f[i][k], f[k+1][j])   i<=k<=(j-1)
    4) that's not the end.... a case when s[i] == s[j], get f[i+1][j-1]. should compare this value to above values in (3), and get the maximum.
 2. how to show the results
    when calculate f[i][j], you can use an array like ans[i][j] to record the way to get f[i][j]. for example, when f[i][j] get maximum when k = k1. so you can record k1 to ans[i][j]. Or f[i+1][j-1] get the maximum , you can record -1 to ans[i][j], or in the case i==j you get the maximum, set ans[i][j] to 0......
    Then you can get result by DFS.

hope it helps :)
Re: some hints
Posted by Dmitriy 12 Feb 2018 14:20
hliu20 wrote 18 May 2013 15:26
    3) if i < j, then f[i][j] = min(f[i][k], f[k+1][j])   i<=k<=(j-1)
   

> f[i][j] = min(f[i][k], f[k+1][j]

You determine f(k) on f(k + 1) in main cycle. But f(k + 1) is undefine for a while.
It's a good hint, but something is wrong.