BZOJ2981 : [Poi2002]括号

时间:2023-11-11 10:17:50

对于最终加入了括号的序列,对其求中缀表达式,建树。

可以发现$n-1$个运算符DFS序递增,且若一个-上方往左走了奇数次,则它就是+,否则就是-。

所以考虑DP,设$f[i][j]$表示考虑了前$i$个运算符,且最右边那条链长度为$j$的方案数。

时间复杂度$O(n^2)$。

#include<cstdio>
#define P 1000000000
int n,i,j,x,ans,f[2][5010];char s[5];
int main(){
scanf("%d%s",&n,s);
if(s[0]=='+')return puts("0"),0;
for(f[0][1]=x=1,i=2;i<n;i++,x^=1){
for(j=i;j;j--)f[x][j]=(f[x][j+1]+f[x^1][j-1])%P;
for(scanf("%s",s),j=s[0]=='+'?1:2;j<=i;j+=2)f[x][j]=0;
}
for(i=1;i<=n;i++)ans=(ans+f[x^1][i])%P;
return printf("%d",ans),0;
}