题解：P7248 [BalticOI 2012] 括号 (Day1)

思路

本题是括号匹配和动态规划，还是比较简单。

已经匹配的括号我们不用管，只需要处理没有匹配的左括号即可。但是考虑到数据范围，普通的二维动态规划空间会炸，需要滚动数组来解决。

f_{i,j}

表示第到

i

个位置，未匹配的左括号个数为

j

，那么就有如下状态转移方程。

不是左括号：

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

题解：P7248 [BalticOI 2012] 括号 (Day1)

文章操作

思路

Code

相关推荐

评论

题解：P7248 [BalticOI 2012] 括号 (Day1)