YZOJ P3384 [校内训练20171201]括号替换问题
时间限制:1000MS 内存限制:262144KB
难度:\(5.0\)
-
问题描述
这里有一个关于合法的括号序列的问题。如果插入“+” 和 “1” 到一个括号序列,我们能得到一个正确的数学表达式,我们就认为这个括号序列是合法的。例如,序列 “(())()”, “()” 和 “(()(()))” 是合法的,但是 “)(“, “(()” 和 “(()))(” 是不合法的。我们有一个仅由 “(”,“)” 和 “?” 组成的括号序列,你必须将 “?” 替换成括号,从而得到一个合法的括号序列。
对于给定仅由 “(”,“)” 和 “?” 组成的括号序列,你需要将 “?” 替换成括号,得到一个合法的括号序列,同时需要使得代价之和最小。
-
数据输入
文件有多个测试实例(\(\leq 5\))。每个实例的第一行有 \(1\) 个正整数 \(n\),(\(1 \leq n \leq 100000\)),表示括号序列的长度为 \(n\)。第二行是一个长度为 \(n\) 的字符串,表示输入的括号序列,字符串仅由 “(”,“)” 和 “?” 组成。接下来 \(m\) 行,\(m\) 是字符串中 “?” 的个数,每一行包含两个整数 \(a_i\) 和 \(b_i\)(\(1 \leq a_i,b_i \leq 1000000\)),\(a_i\) 是将第 \(i\) 个 “?” 替换成左括号的代价,\(b_i\) 是将第 \(i\) 个 “?” 替换成右括号的代价。文件的最后一行有一个 \(0\) 表示结束。
-
结果输出
将计算出的每个测试实例的答案依次输出到文件中。每个测试实例第一行输出一个整数,表示最小代价和。如果不存在合法方案,输出 \(-1\)。如果存在合法方案,第二行输出替换后的括号序列。若有多种替换方案的代价之和最小,可以输出任意一种。…