栈+括号序列+暴力枚举——cf1248D1

这个复杂度首先就想到是n3的复杂度，n2枚举换的位置，求值在花费n复杂度

判断一个序列有多少独立的括号子串时用栈处理一下即可

/*
枚举交换两个括号的位置，然后再对新的序列判一次即可 
*/
#include<bits/stdc++.h>
using namespace std;
#define N 1005
char s[N];
int n,ans[N][N];
 
int calc(){
    stack<int>stk;
    while(stk.size())
        stk.pop(); 
    int res=0,len=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='(')
            stk.push(0);
        else if(s[i]==')'){
            if(stk.size() && stk.top()==0){
                stk.pop();
                if(stk.size()==len)
                    res++;//一段完整的括号序列结束了 
            }
            else {
                res=0;
                stk.push(1);
                len++;
            }
        }
    }
    
    int cnt0=0,cnt1=0;
    while(stk.size()){
        if(stk.top()==0)
            cnt0++;
        else cnt1++;
        stk.pop();
    }
    if(cnt0 && cnt1 && cnt0==cnt1)res++;
    if(cnt0 !=cnt1)res=0;
    return res;
}
 
int main(){
    cin>>n;
    scanf("%s",s+1);
    
    int c1=0,c2=0;
    for(int i=1;i<=n;i++)
        if(s[i]=='(')c1++;
        else c2++;
    if(c1!=c2){
        cout<<0<<endl;
        cout<<"1 1"<<'
';
        return 0;
    }
    
    int Max=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            swap(s[i],s[j]);
            ans[i][j]=calc();
            Max=max(Max,ans[i][j]);
            swap(s[i],s[j]);    
        }
        
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(ans[i][j]==Max){
                cout<<Max<<'
';
                cout<<i<<" "<<j<<'
';
                return 0;
            }
    
}