比赛 EYOI暨SBOI暑假快乐赛5th 评测结果 EEEEEEEEEE
题目名称 Famil Door and Brackets 最终得分 0
用户昵称 康尚诚 运行时间 1.953 s
代码语言 C++ 内存使用 8.86 MiB
提交时间 2022-06-29 11:07:55
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
stack<int> st;
map<string,int> front,behind;
int n,m,ans=0;
string s;
bool check(string str)
{
    bool ok=true;
    for(int i=0;i<str.length()&&ok;i++)
    {
        if(str[i]=='(') st.push(1);
        else
        {
            if(st.empty()) ok=false;
            else st.pop();
        }
    }
    while(!st.empty())
    {
        ok=false;st.pop();
    }
    return ok;
}
int dfs(string frt,string bhd,int len,int frt1,int frt2,int bhd1,int bhd2)
{
    if(len==n-m)
    {
        string fnl=frt+s+bhd;
        if(check(fnl)&&(front[frt]==0||behind[bhd]==0))
        {
//            cout<<frt<<" "<<bhd<<endl; 
            front[frt]=1;behind[bhd]=1;
            ans++;
        }
        return 0;
    }
    dfs(frt+'(',bhd,len+1,frt1+1,frt2,bhd1,bhd2);
    if(frt1>frt2)//如果前子串左括号个数大于右括号(否则再增加右括号必定不匹配) 
    {
        dfs(frt+')',bhd,len+1,frt1,frt2+1,bhd1,bhd2);
    }
    if(bhd1<bhd2)//后子串右括号个数大于左括号(同上)
    {
        dfs(frt,'('+bhd,len+1,frt1,frt2,bhd1+1,bhd2);
    } 
    dfs(frt,')'+bhd,len+1,frt1,frt2,bhd1,bhd2+1);
}
int main()
{
    freopen("tribrackets.in","r",stdin);
    freopen("tribrackets.out","w",stdout);
    cin>>n>>m>>s;
    if(n==m)
    {
        if(check(s))
        {
            cout<<"1"<<endl;return 0;
        }
        else
        {
            cout<<"0"<<endl;return 0;
        }
    }
    dfs("","",0,0,0,0,0);
    cout<<ans;
    return 0; 
}