Submission #1863853

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

string s;
int sz;
int dp[110][110][110];

int main(void) {
  cin >> s;
  sz = s.size();

  fill(dp[0][0], dp[110][0], 1 << 20);
  dp[0][0][0] = 0;
  for (int i = 0; i < sz; i++) {
    for (int j = 0; j < sz; j++) {
      for (int k = 0; k < sz; k++) {
        if (s[i] == '(') {
          dp[i + 1][j][k + 1] = min(dp[i + 1][j][k + 1], dp[i][j][k]);
          if (k > 0) {
            dp[i + 1][i][k - 1] = min(dp[i + 1][i][k - 1], dp[i][j][k] + 1);
          }
        } else {
          if (k > 0) {
            dp[i + 1][j][k - 1] = min(dp[i + 1][j][k - 1], dp[i][j][k]);
          }
          dp[i + 1][i][k + 1] = min(dp[i + 1][i][k + 1], dp[i][j][k] + 1);
        }
      }
    }
  }

  int ans = 1 << 20;
  for (int i = 0; i < sz; i++) {
    ans = min(ans, dp[sz][i][0] + i);
  }
  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result