Balanced Cow Breeds
提交数: 2, 通过率: 50%, 平均分: 50
题目描述:
农夫约翰通常会给奶牛打上圆形烙印。
但是烙印坏了，所以他现在只能给奶牛打上括号形 – ( 的烙印了。
他的农场中有两种奶牛：荷斯坦牛和根西岛牛。
他给每头奶牛打上括号形状的烙印。
根据奶牛所面向的方向，这可能看上去像是左括号或右括号。
约翰的 N 头奶牛排成一排，每头朝向任意方向，因此奶牛上的标记看上去像是长度为 N 的一串括号序列。
看着这个序列，约翰发现如果他从左到右扫过所有荷斯坦牛，按它们在序列中出现的顺序，就可以得到一串平衡的括号。
根西岛牛也是如此！
为了确定这是否是一个罕见的情况，请帮助约翰计算共有多少种指定奶牛品种的不同方案可以使上述特点成立。
有若干种定义括号字符串是否“平衡”的方式。
最简单的定义为字符串所包含的 ( 和 ) 数量必须相同，并且对于字符串的任意前缀，所包含的 ( 的数目都不少于 ) 的数目。
例如，以下字符串都是平衡的：
()
(())
()(()())
以下则不是：
)(
())(
((())))输入格式:
一个长度为 N 的括号序列。
输出格式:
输出能够满足条件的指定奶牛品种的不同方案的数量对 2012 取模后的结果。
可以所有奶牛都为同一个品种。
数据范围:
1≤N≤1000
样例输入:
(())
样例输出:
6
提示:
下面是所有可行的奶牛品种指定方案：
(())
HHHH
(())
GGGG
(())
HGGH
(())
GHHG
(())
HGHG
(())
GHGH空间限制: 128MB
来源: Usaco2012 NOV Silver/Gold