Submission #1846694

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

string s;
int memo[110][110][110];

int rec(int cur, int pre, int miss, int diff) {
  if (diff < 0) return 1 << 30;
  if (memo[pre][miss][diff] > 0) return memo[pre][miss][diff];
  if (cur == s.size()) {
    if (diff == 0) return memo[pre][miss][diff] = pre + miss;
    return memo[pre][miss][diff] = 1 << 30;
  }

  int res = 1 << 30;
  if (s[cur] == '(') {
    res = min(res, rec(cur + 1, pre, miss, diff + 1));
    res = min(res, rec(cur + 1, cur, miss + 1, diff - 1));
  } else {
    res = min(res, rec(cur + 1, cur, miss + 1, diff + 1));
    res = min(res, rec(cur + 1, pre, miss, diff - 1));
  }
  return memo[pre][miss][diff] = res;
}

int main(void) {
  cin >> s;
  fill(memo[0][0], memo[110][0], -1);
  cout << rec(0, 0, 0, 0) << endl;  

  return 0;
}

Submission Info

Judge Result