分数: 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 已经是一个平衡的字符串。