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\)。如果存在合法方案，第二行输出替换后的括号序列。若有多种替换方案的代价之和最小，可以输出任意一种。…