分数: 400 点
问题陈述
给你一个字符串 S 长度 2N 由字符组成 ( 和 )。让 S_i 表示 i从左边算起第一个字符 S.
您可以按任意顺序执行以下两种类型的操作零次或多次:
-
选择一对整数 (i,j) 这样 1\leq i < j \leq 2N。互换 S_i 和 S_j。该操作的成本是 A.
-
选择一个整数 i 这样 1\leq i \leq 2N。更换 S_i 与
(or)。该操作的成本是 B.
你的目标是 S 正确的括号序列。找出实现这一目标所需的最低总成本。可以证明,用有限次数的操作总能实现目标。
什么是正确的括号序列?
正确的括号序列是满足以下任一条件的字符串:- 这是一个空字符串。
- 由连接而成
(, A,)按此顺序,其中 A 是正确的括号序列。 - 由连接而成 A 和 B 按此顺序,其中 A 和 B 是正确的括号序列。
约束
- 所有输入值均为整数。
- 1 \leq N \leq 5\times 10^5
- 1\leq A,B\leq 10^9
- S 是一个长度为 2N 由字符组成
(和).
输入
输入由标准输入按以下格式给出:
N A B S
输出
在一行中打印答案。
示例输入 1
3 3 2 )))(()
示例输出 1
5
这是一种操作方法:
- 交换 S_3 和 S_4. S 变为
))()()。成本是 3. - 替换 S_1 与
(. S 变为()()(),这是正确的括号序列。成本是 2.
在这种情况下,我们做了 S 总成本的正确括号序列 5。没有办法制作 S 小于的正确括号序列 5.
示例输入 2
1 175 1000000000 ()
示例输出 2
0
给定 S 已经是正确的括号序列,因此不需要进行任何操作。
示例输入 3
7 2622 26092458 ))()((((()()((
示例输出 3
52187538