CF3D Least Cost Bracket Sequence

题目描述

This is yet another problem on regular bracket sequences.

A bracket sequence is called regular, if by inserting "+" and "1" into it we get a correct mathematical expression. For example, sequences "(())()", "()" and "(()(()))" are regular, while ")(", "(()" and "(()))(" are not. You have a pattern of a bracket sequence that consists of characters "(", ")" and "?". You have to replace each character "?" with a bracket so, that you get a regular bracket sequence.

For each character "?" the cost of its replacement with "(" and ")" is given. Among all the possible variants your should choose the cheapest.

输入格式

The first line contains a non-empty pattern of even length, consisting of characters "(", ")" and "?". Its length doesn't exceed $5·10^{4}$ . Then there follow $m$ lines, where $m$ is the number of characters "?" in the pattern. Each line contains two integer numbers $a_i$ and $b_i$ ($1<=a_i,b_i<=10^6$ ), where is $a_i$the cost of replacing the $ i-th$ character "?" with an opening bracket, and $b_i$ — with a closing one.

输出格式

Print the cost of the optimal regular bracket sequence in the first line, and the required sequence in the second.

Print -1, if there is no answer. If the answer is not unique, print any of them.

题意翻译

给一个序列，序列里面会有左括号、问号、右括号。对于一个‘？’而言，可以将其替换为一个 '(' ，也可以替换成一个 ')' ，但是都有相应的代价。问：如何替换使得代价最小。前提是替换之后的序列中，括号是匹配的。如果不能替换为一个括号匹配的序列则输出-1。

输入:

第一行是序列，序列长度不超过5*10^4，下面m(m是？的数量)行有每行2个数据，第一个是 '(' 的代价，第2个是 ')' 的代价

输出：

第一行打印代价，第二行打印替换后的序列。不行输出-1

样例

输入 #1

(??)
1 2
2 8

输出 #1

4
()()

题解

这一题是一道使用优先队列和贪心的数据结构题。题目要求我们在括号序列合法的情况下，求出最小代价。

首先我们考虑括号序列合法。一个合法的括号字符串一定是左括号数等于右括号， 如果我们从左向右遍历，一定不能出现右括号多于左括号的情况（左括号多于右括号可以用后面可能存在的右括号弥补）。

然后考虑代价最小。需要求代价最小的括号字符串，那我们需要保证全局的最优，我们需要可以对之前的已经确定的字符串进行修改。从左向右遍历时，在保证左括号数大于或等于右括号数的情况下，我们将所有的 ‘?’ 看作右括号，当出现右括号多于左括号情况时，将之前一个 ’?’ 变成的右括号变成左括号（如果是遇到 ‘?’ ，那么也可以选择自身）。如果出现没有多余的 ‘?’ 可以变成左括号，那么说明无法构成合法的括号序列。那么让代价最小，只需要在将之前一个 ’?’ 变成的右括号变成左括号这一步选出最优的 ’?’ 变成的右括号即可。

那么我们结合上面两步，我们可以注意到 一个 ’?’ 变成的右括号变成左括号时，对代价的贡献是：$r[i] +(l[i]-r[i])$ 。所以当转变时，我们选择前面 $l[i]-r[i]$ 最小的 ’?’ 就好了。

至于代码如何实现，我们可以用一个值num记录左括号比右括号多几个，遇到左括号num+=1;遇到右括号num-=1；对每一个遇到的 ’?’ 都将他们丢入优先队列（按照 $l[i]-r[i]$ 从小到大排序）同时num-=1。当需要转变（num<0）时，便出队列一个，总代价加上 $l[i]-r[i]$ ,num+=2。如果需要转变但优先队列为空，则无法构成合法括号序列。如果遍历字符串结束后，左括号多于右括号（num>0）,则无法构成合法括号序列。总复杂度O(nlogn)

（记得开long long！）

代码

贴上过题代码。

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;

typedef struct {
  int val;
  int num;
}P;

struct cmd {
  bool operator()(const P &a, const P &b) { return a.val > b.val; }
};

string str;
int l[maxn], r[maxn];
priority_queue<P, vector<P>, cmd> que;
int main() {
  cin >> str;
  int len = str.size();
  for (int i = 0; i < len; i++) {
    if (str[i] == '?') {
      cin >> l[i] >> r[i];
    }
  }
  int flag = 0;
  int num = 0;
  ll sum = 0;
  for (int i = 0; i < len; i++) {
    if (str[i] == '(') {
      num++;
    }  
    else if (str[i] == ')') {
      num--;
    }
    else {
        num--;
        sum += r[i];
        que.push(P{l[i] - r[i], i});
        str[i] = ')';
    }
    if (num < 0) {
      if (que.size() == 0) {
        flag = 1;
        break;
      }
      P p = que.top();
      que.pop();
      sum += p.val;
      str[p.num] = '(';
      num += 2;
    }
  }
  if (flag == 0 && num == 0) {
    cout << sum << endl;
    cout << str;
  } else
    cout << -1;
  return 0;
}