← 返回题目列表

AtCoder · arc175_b

B. 括号排列

中文机器翻译题面 查看原题

分数: 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