链接:https://www.nowcoder.com/acm/contest/188/D
来源:牛客网
题目描述
小w很生气
小w有一个长为n的括号序列
愤怒小w想把这个括号序列分为两个括号序列
小w想让分为的这两个括号序列同时合法
小w想知道一共有多少种划分方案
愤怒小w想把这个括号序列分为两个括号序列
小w想让分为的这两个括号序列同时合法
小w想知道一共有多少种划分方案
(划分的意思是划分为两个子序列)
注意两个序列是 A,B 和 两个序列是B,A 算两种方案,也就是同一位置位于不同划分为方案不同
输入描述:
第一行一正整数n
第二行,一串长为n的括号序列
输出描述:
一个正整数
表示对方案数对2333取mod后的方案数
输入例子:
4
(())
输出例子:
6
-->
备注:
n ≤ 10000 想法:
1 把'('看作是1,')'看作是-1;
2 维护A序列的前缀和 dp[i][k] : 对于在前i个字符中取子序列作为A,其和为k的方法有多少种