Submission #1695752

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}

const int MAX_N = 110;

int dp[MAX_N][MAX_N][MAX_N];

int main() {
#ifdef LOCAL_TEST
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    string s;
    cin >> s;
    int n = s.size();
    rep(i, MAX_N) rep(j, MAX_N) rep(k, MAX_N) dp[i][j][k] = 1e9;
    dp[0][0][0] = 0;

    rep(i, n) rep(j, n) rep(k, n) {
        if(dp[i][j][k] == 1e9) continue;
        if(s[i] == '(') {
            chmin(dp[i+1][j+1][k], dp[i][j][k]);
            if(j > 0) chmin(dp[i+1][j-1][i], dp[i][j][k]+1);
        }
        else {
            if(j > 0) chmin(dp[i+1][j-1][k], dp[i][j][k]);
            chmin(dp[i+1][j+1][i], dp[i][j][k] + 1);
        }
    }

    int ans = 1e9;
    rep(i, n) ans = min(ans, dp[n][0][i]+i);
    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result