比赛 |
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;
}