比赛 EYOI暨SBOI暑假快乐赛5th 评测结果 TTTTTTTTTT
题目名称 Famil Door and Brackets 最终得分 0
用户昵称 䱖虁職 运行时间 20.000 s
代码语言 C++ 内存使用 6.23 MiB
提交时间 2022-06-29 11:21:46
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,d,ans=0;
string p="",s,q="";
bool judge(string s)
{
    int num=0,l=s.length();
    for(int i=0;i<l;i++)
    {
        if(s[i]=='(')num++;
        else num--;
        if(num<0)return 0;
    }
    if(num!=0)return 0;
    return 1;
}
int dfs()
{
    if(judge(p+s+q))
    {
        ans++;
        return 0;
    }
    else
    {
        for(int i=0;i<=d;i++)
        {
            int j=d-i;
            for(int k=1;k<=j;k++)
            {
                for(int l=1;l<=2;l++)
                {
                    for(int o=1;o<=2;o++)
                    {
                        if(l==1)p+="(";
                        else p+=")";
                        if(o==1)q+="(";
                        else q+=")";
                        dfs();
                        int l1=p.length(),l2=q.length();
                        p[l1-1]='0';
                        q[l2-1]='0';
                    }
                }
            }
        }
    }
}
int main(){
    freopen("tribrackets.in","r",stdin);
    freopen("tribrackets.out","w",stdout);
    cin>>n>>m>>s;
    int l=s.length();
    if(n==m)
    {
        puts("1");
        return 0;
    }
    else
    {
        d=n-m;
        int lt=0,rt=0;
        for(int i=0;i<l;i++)
        {
            if(s[i]=='(')lt++;
            else rt++;
        }
        if(abs(lt-rt)>d)puts("0");
        dfs();
        printf("%d\n",ans);
        return 0;
    }
}