题解：P7248 [BalticOI 2012] 括号 (Day1)
chenyizhen
·
·
题解
思路
本题是括号匹配和动态规划，还是比较简单。
已经匹配的括号我们不用管，只需要处理没有匹配的左括号即可。但是考虑到数据范围，普通的二维动态规划空间会炸，需要滚动数组来解决。
不是左括号：$f_{i,j}=f_{i-1,j}$。
是左括号：$f_{i,j}=f_{i-1,j-1}+f_{i-1,j+1}$。
别忘了取模！！！
---
### Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5,mod=1e9+9;
void read(int &a){
char ch;int f=1,k=0;ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
a=k*f;
}
int n,f[2][N];
char ch;
signed main(){
read(n);
f[0][0]=1;
for(int i=1;i<=n;i++){
cin>>ch;
int minn=min(i,n-i);
for(int j=0;j<=minn;j++){
if(j==0||ch==')') f[i%2][j]=f[(i+1)%2][j+1];
else f[i%2][j]=(f[(i+1)%2][j+1]+f[(i+1)%2][j-1])%mod;
}
}
cout<<f[n%2][0];
return 0;
}
```