A7412 | $小安的括号调整$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

小枫、小午和小安三个人在玩一个字符串游戏。 小枫在黑板上写了一个长度为 $2N$ 的字符串 $S$，只由 ( 和 ) 两种字符组成。 小午可以向小安提出两种修改操作，每次操作需要付出一定的代价： 1. 交换操作：选择 $1 \leq i < j \leq 2N$，交换 $S_i$ 和 $S_j$，代价为 $A$。 2. 替换操作：选择 $1 \leq i \leq 2N$，将 $S_i$ 改为 ( 或 )，代价为 $B$。 小安的目标是通过任意顺序、任意次数的操作，将 $S$ 变成一个合法的括号序列，并使得总代价最小。 小午想知道这个最小代价是多少。你能帮小安算出来吗？ 合法括号序列的定义： >空字符串是一个合法括号序列。如果 $A$ 是一个合法括号序列，那么 ( + $A$ + ) 也是一个合法括号序列。如果 $S$ 和 $T$ 都是非空的合法括号序列，那么 $S + T$ 也是一个合法括号序列。可以证明，经过有限次操作后，一定可以将 $S$ 变成合法括号序列。

第一行输入三个正整数 $N,A,B$ ，分别表示字符串长度的一半，一次交换操作的代价，一次替换操作的代价。 第二行输入一个长度为 $2N$ 的字符串 $S$ ，仅由 (和) 组成。

输出一行一个整数，表示将 $S$ 变为合法括号序列所需的最小总代价。

输入 #1

3 3 2
)))(()

输出 #1

C++ 编辑器

输入

输出