Advertisement
AntonGorokhov

Untitled

Oct 6th, 2022
556
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5. string s;
  6. int mas[100][100];
  7. string massive[100][100];
  8.  
  9. int f(int L, int R)
  10. {
  11.     if(mas[L][R] == -1)
  12.     {
  13.         int range,nowa;
  14.         if(L > R)
  15.         {
  16.             mas[L][R] = 0;
  17.             massive[L][R] = "";
  18.         }else if(L == R)
  19.         {
  20.             mas[L][R] = 1;
  21.             massive[L][R] = "";
  22.         }else
  23.         {
  24.         // ...
  25.         mas[L][R] = R-L+1;// as if we changed everything
  26.         if( ((s[L] == '(') && (s[R] == ')')) || ((s[L] == '[') && (s[R] == ']')) || ((s[L] == '{') && (s[R] == '}')) )
  27.         {
  28.             mas[L][R] = f(L+1,R-1);
  29.             massive[L][R] = s[L] + massive[L+1][R-1] + s[R];
  30.         }
  31.         for(range = L; range < R; ++range)
  32.         {
  33.             nowa = f(L,range) + f(range+1,R);
  34.             if(mas[L][R] > nowa)
  35.             {
  36.                 mas[L][R] = nowa;
  37.                 massive[L][R] = massive[L][range] + massive[range+1][R];
  38.             }
  39.         }
  40.         }
  41.     }
  42.     return mas[L][R];
  43. }
  44.  
  45. int main()
  46. {
  47.     cin >> s;
  48.     int n = s.length();
  49.  
  50.     for(int i = 0; i < n; ++i)
  51.     {
  52.         for(int j = 0; j < n; ++j)
  53.         {
  54.             mas[i][j] = -1;
  55.             massive[i][j] = "";
  56.         }
  57.     }
  58.     for(int i = 0; i < n; ++i)
  59.     {
  60.         mas[i][i] = 1;// delete 1 symbol to get 'good' brackets;
  61.     }
  62.     int answer = f(0,n-1);
  63.     /*
  64.     cout << endl << answer << endl << massive[0][n-1] << endl << endl;
  65.  
  66.     for(int i = 0; i < n; ++i)
  67.     {
  68.         for(int j = 0; j < n; ++j)
  69.         {
  70.             cout << mas[i][j] << " ";
  71.         }
  72.         cout << endl;
  73.     }*/
  74.     cout << massive[0][n-1];
  75.     return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement