daily pastebin goal
17%
SHARE
TWEET

G0$Y/-

a guest Dec 18th, 2017 45 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main() {
  6.     string str;
  7.     cin >> str;
  8.     vector<vector<int>> dp(str.size(), vector<int> (str.size()));
  9.     for (int i=0; i<str.size(); i++)
  10.         for (int j=i; j>=0; j--) {
  11.             if (i == j) dp[j][i] = 1;
  12.             else {
  13.                 int min=1000;
  14.                 if (((str[j] == '(') && (str[i] == ')')) || ((str[j] == '[') && (str[i] == ']')) || ((str[j] == '{') && (str[i] == '}'))) min=dp[j+1][i-1];
  15.                 for (int k=j; k<i; k++) if (dp[j][k]+dp[k+1][i]<min) min=dp[j][k]+dp[k+1][i];
  16.                 dp[j][i]=min;
  17.             }
  18.         }
  19.     cout << (str.size()-dp[0][str.size()-1]);
  20. }
RAW Paste Data
Top