ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
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.
Re: some hints
Posted by imaginary friend 16 Oct 2018 03:54
actually it's correct. he is going by the increasing of the first parameter. it's like he is splitting the string, trying to get answer for a bigger string based on the smaller substrings