v 0. Pasted by slipstak2 as cpp at 2011-01-08 14:41:04 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 13.
  2. // 13С. Скобки(3) [bracket3]
  3. // ibelyaev: 06Jan2011
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <string>
  8. #include <vector>
  9.  
  10. using namespace std;
  11. const int MAX_VALUE = 1e9;
  12. int n;
  13. string str;
  14. vector<vector<int> > mas;
  15. void input()
  16. {
  17.     cin>>str;
  18.     n = str.size();
  19.     mas = vector<vector<int> >(n,vector<int>(n,0));
  20. }
  21. string open = "([";
  22. string clos = ")]";
  23. bool isPair(char f, char s)
  24. {
  25.     int posF = open.find(f);
  26.     int posS = clos.find(s);
  27.     return posF == posS && posF != -1;
  28. }
  29. string Pair(char one)
  30. {
  31.     int pos = open.find(one);
  32.     if (pos == -1)
  33.         pos = clos.find(one);
  34.    
  35.     return string(&open[pos],1) + string(&clos[pos],1);
  36. }
  37. string getAnswer(int l, int r)
  38. {
  39.     if (l > r) return "";
  40.     if (l == r)
  41.         return Pair(str[l]);
  42.     int border = (isPair(str[l],str[r]) ? mas[l+1][r-1] : MAX_VALUE);
  43.     if (border == mas[l][r])
  44.         return str[l] + getAnswer(l+1,r-1) + str[r];
  45.     for (int m = l; m < r; m++)
  46.     {
  47.         if (mas[l][m] + mas[m+1][r] == mas[l][r])
  48.             return getAnswer(l,m) + getAnswer(m+1,r);
  49.     }
  50. }
  51. void solve()
  52. {
  53.     for (int i=0;i<n;i++)
  54.         mas[i][i] = 1;
  55.     for (int len = 1; len < n; len++) {
  56.         for (int i=0;i<n;i++) {
  57.             int j = i + len;
  58.             if (j>=n) break;
  59.  
  60.             int curLen = MAX_VALUE;
  61.             if (isPair(str[i],str[j]))
  62.                 curLen = mas[i+1][j-1];
  63.             for (int m = i; m < j; m++)
  64.                 curLen = min(curLen, mas[i][m] + mas[m+1][j]);
  65.             mas[i][j] = curLen;
  66.         }
  67.     }
  68.  
  69.     string answer = "";
  70.     answer = getAnswer(0,n-1);
  71.     cout<<answer;
  72. }
  73. int main()
  74. {
  75.     freopen("input.txt","r",stdin);
  76.     freopen("output.txt","w",stdout);
  77.  
  78.     input();
  79.     solve();
  80.     return 0;
  81. }


Editing is locked.