#2421. 序列变换
序列变换
序列变换
题目描述
NOI2022 省选 DAY2 序列变换(bracket) 序列变换(bracket) 【题目描述】 你手里有一个长度为2n 的合法括号序列s。s 的每一个左括号有一个权值。 在你眼中,不同的括号序列带来的视觉美感不尽相同。因此,你对具有某一种结构 的括号序列特别喜欢,而讨厌具有其他一些结构的括号序列。你希望对s 进行一些变换, 以消除掉一些自己不喜欢的结构。 具体而言,形如(A()B) (其中A,B 均为合法括号序列,下同)的结构是你喜欢的, 而形如(A)(B) 的结构是你不喜欢的。你有两种操作来改变括号之间的位置。 这两种操作如下: • 操作1:交换形如p(A)(B)q 的串中A 和B 之间的两个括号,变换为p(A()B)q (其中p,q 为任意串,可以为空,但不一定分别为合法括号序列,下同),它的代 价为x 乘(A) 中第一个左括号的权值加上y 乘(B) 中第一个左括号的权值,其 中x, y ∈{0, 1}; • 操作2:交换形如pABq 的串中的A 和B,变换为pBAq ,这个操作不需要代价。 注意:交换的时候所有左括号的权值是跟着这个括号一起交换的。 你现在想知道的是,将s 变换为一个不包含你不喜欢的结构的括号序列至少需要多 少代价? 【输入格式】 从文件bracket.in 中读入数据。 第一行三个整数n, x, y。 第二行一个长度为2n 的合法括号序列,表示s。 第三行n 个正整数,其中第i 个表示左数第i 个左括号的权值。 【输出格式】 输出到文件bracket.out 中。 一行一个整数,表示把s 变换为一个不包含你不喜欢的结构的括号序列至少需要的 代价。 【样例1 输入】 1 2 0 1 2 ()() 3 1 3 第4 页 共8 页
NOI2022 省选 DAY2 序列变换(bracket) 【样例1 输出】 1 1 【样例1 解释】 最优方案是先使用操作2 交换两对括号,然后使用操作1(此时A,B,p,q 都是空 串)交换中间的两个括号,代价为B 左边那个括号的权值,也就是1。最后得到括号序 列(()),不包含你不喜欢的结构。 【样例2 输入】 1 2 1 0 2 ()() 3 1 3 【样例2 输出】 1 1 【样例2 解释】 最优方案是直接使用操作1,因为此时计算代价的方式不同了,这次只算A 左边的 那个括号的权值作为代价。 【样例3】 见选手目录下的bracket/bracket3.in 与bracket/bracket3.ans。 【子任务】 保证2 ≤n ≤400000,0 ≤x, y ≤1 。 保证所有的权值在[1, 107] 之内。 第5 页 共8 页
NOI2022 省选 DAY2 序列变换(bracket) 测试点编号 特殊限制 1 ∼3 n ≤8 4 ∼5 所有权值均相等 6 ∼8 n ≤20 9 ∼12 x = 0, y = 1 13 ∼16 n ≤2000 17 ∼25 无特殊限制 【提示】 称一个字符串s 为合法括号序列,当且仅当s 仅由数量相等的字符( 和) 组成,且 对于s 的每一个前缀而言,其中( 的数量均不少于) 的数量。特别地,空串也是合法 括号序列。 第6 页 共8 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2 0 1
()()
1 3
1
样例 2
2 1 0
()()
1 3
1