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

Solution
Posted by askhatik 26 Feb 2012 05:41
the solution is dp:)
dp[i][j] - contains min number of brackets of type '(', '[' for interval from i to j, that is necessary to paste in order to sequence become correct.
if i'th symbol is opened bracket and jth is corresponding closing, then we can improve anser for this interval: dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + 2);
if there are different brackets, then we can improve in such way:
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 2;
and finally we can improve by other bracket in the middle:
dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j] + 2);
here, k is the position of all indices that is corresponding closing bracket for i-th;
for example if(s[i] == '(') then k is the index of all
k where, s[k] = ')';
here simple code:
for(int i = 2; i < n; ++i) {
         for(int j = 0; j + i < n; ++j) {
             if(isOpened(s[j]) && s[j] == get(s[j + i])){
//get(c) returns corresponding closing bracket for bracket c;
                  d[j][j + i] = d[j + 1][j + i - 1] + 2;

             }
             else{
                 if(d[j + 1][j + i] < d[j][j + i - 1]) {
                      d[j][j + i] = d[j + 1][j + i] + 2;

                  }
                  else{
                       d[j][j + i] = d[j][j + i - 1] + 2;

                  }
             }
             if(isOpened(s[j]))
                 for(int k = j; k < j + i; ++k)
                       if(get(s[j]) == s[k]){
                            if(d[j + 1][k - 1] + 2 + d[k + 1][j + i] < d[j][j + i]) {
                                 d[j][j + i] = d[j + 1][k - 1] + 2 + d[k + 1][j + i];

                            }
                       }
         }
    }

don't forget to precount for length 1 and 2 :)
good luck to everybody :)