3762: 括号序列(第一轮04)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
一个长度为n 的合法括号序列， 每对匹配括号可以不染色、染白色、染黑色， 染白色和黑色 分别有对应的代价， 分别是a和b。相邻的非配对括号不能同色（都不染色也属于同色）， 问 染色后的序列的最大代价。
序列的代价是每对配对括号的代价和。 每对配对的括号必须染相同的颜色。
合法的括号序列是指由左括号"("和右括号")"组成的序列，满足以下条件：
1. 每个左括号都必须有对应的右括号，且右括号的位置必须在左括号之后。
2. 括号必须按照正确的嵌套关系闭合，即在任意位置，左括号的数量必须等于右括号的数 量，并且左括号必须先闭合。
例如， 以下序列是合法的括号序列： - ()
- ((()))
- ()()()
- (()(()))
而以下序列是不合法的括号序列：
- (：没有对应的右括号。
- ())：右括号在左括号之前闭合。
- (()))：右括号数量多于左括号数量。
输入
第一行输入三个正整数 n, a, b。
第二行输入长度为 n 的合法括号序列。
输出
输出一个数，表示染色后的序列的最大代价
样例输入 复制
4 2 3 ()()样例输出 复制
5提示
【样例 1 输入】
4 2 3 ()()
【样例 1 输出】
5
【样例 2 输入】
6 2 3 ((()))
【样例 2 输出】
8
【备注】
对于所有测试点， 1 ≤ a, b ≤ 1000。
- 对于测试点 1： 2 ≤ n ≤ 10。
- 对于测试点2~5： 2 ≤ n ≤ 1000。括号序列嵌套层数至多是1，即()()()() …。
- 对于测试点6~ 10： 2 ≤ n ≤ 1000。