Submission #3374485

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint,int> P1;
typedef pair<int,pint> P2;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007;
const ll INF=1e18;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

string s;
int dp[101][101][101];

signed main(){
    cin.tie(0);
	ios::sync_with_stdio(false);
    cin>>s;
    int n=s.size();
    rep(i,0,n+1)rep(j,0,n+1)rep(k,0,n+1)dp[i][j][k]=INF;
    dp[0][0][0]=0;
    
    rep(i,0,n)rep(j,0,n)rep(k,0,n+1)if(dp[i][j][k]!=INF){
        if(s[i]=='('){
            dp[i+1][j][k+1]=min(dp[i+1][j][k+1],dp[i][j][k]);
            if(0<k)dp[i+1][i][k-1]=min(dp[i+1][i][k-1],dp[i][j][k]+1);
        }else{
            dp[i+1][i][k+1]=min(dp[i+1][i][k+1],dp[i][j][k]+1);
            if(0<k)dp[i+1][j][k-1]=min(dp[i+1][j][k-1],dp[i][j][k]);
        }
    }
    
    int ans=INF;
    rep(j,0,n)ans=min(ans,dp[n][j][0]+j);
    cout<<ans<<endl;
    
    
    
    
    
    
    
    return 0;
}

Submission Info

Judge Result