← 返回题目列表

AtCoder · past202004_k

K. 括号

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

分数: 6 点

警告

2020 年 5 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。

考试结束后,您可以向其他人透露您的总分和等级,但仅此而已(例如,您解决了哪些问题)。

问题陈述

给定的是一个字符串 S 长度 N 组成 (和 )s。让 S_i 表示 i- 第一个字符 S.

我们想要 S a 平衡 字符串(定义如下)。

首先,我们执行以下操作零次或多次:

  • 选择一个整数 1 \leq i \leq N。如果 S_i is (,替换为 );如果 S_i is ),替换为 (。该操作的成本是 C_i.

然后,我们进行如下操作:

  • 选择零个或多个(可能是全部)字符 S 并删除它们。然后,连接剩余的字符 S 不改变顺序。

找出制造所需的最低总成本 S 平衡的字符串。

平衡字符串是以下字符串之一:

  • 空字符串;
  • 的串联 A 和 B 按此顺序,对于一些非空平衡字符串 A 和 B;
  • 的串联 (, A,和 ) 按照这个顺序,对于一些平衡的字符串 A/

约束

  • 1 \leq N \leq 3000
  • 的长度 S is N.
  • 每个字符 S is ( or ).
  • 1 \leq C_i \leq 10^9
  • 1 \leq D_i \leq 10^9
  • N, C_i,和 D_i 是整数。

输入

输入由标准输入按以下格式给出:

N
S
C_1 C_2 \cdots C_N
D_1 D_2 \cdots D_N

输出

打印制作所需的最低总成本 S 平衡的字符串。


示例输入 1

3
))(
3 5 7
2 6 5

示例输出 1

8

S 最初是 ))(。使其成为平衡弦的一种方法是:

  • 在“修改”步骤中,更改 S_1 的代价是 3. S 变为 ()(.
  • 在“删除”步骤中,删除 S_3 的代价是 5. S 变为 ().

这里的总成本是 3+5=8,这是最小可能值。


示例输入 2

1
(
10
20

示例输出 2

20

S 最初是 (,唯一的选择就是将其设为空字符串。


示例输入 3

10
))())((()(
13 18 17 3 20 20 6 14 14 2
20 1 19 5 2 19 2 19 9 4

示例输出 3

18

示例输入 4

4
()()
17 8 3 19
5 3 16 3

示例输出 4

0

S 已经是一个平衡的字符串。