题目地址：Codeforces：Problem – 3D – Codeforces、洛谷：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.

题意简述

给一个含不确定字符?的括号序列，每个?替换成(花费为$a_i$，替换成)花费为$b_i$，问将所有?替换为括号后使得最后得到一个完全匹配的括号序列的最小花费。

输入输出格式

输入格式：
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 ai and bi (1 ≤ ai,  bi ≤ 10^6), where ai is the cost of replacing the i-th character “?” with an opening bracket, and bi — 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：

(??)
1 2
2 8

输出样例#1：

4
()()

题解

很有意思的一个题目，第一即视感是DP，事实上确实也可以DP做。

DP的思路是，令状态$dp(i, j)$表示到了第$i$个字符的位置，且前面有$j$个未匹配的左括号的最小花费，转移时可以枚举每个?是替换成左括号还是右括号来确定，即
$$ dp(i, j) = \min \{ dp(i – 1, j – 1) + a_i, dp(i – 1, j + 1) + b_i \} $$
另处理一下$j=0$及$i=0$或$i=n$的边界情况即可。
问题在于，这个DP的空间复杂度是$O(n^2)$并存不下$5 \times 10^4$这个规模的数据。即使可以用滚动数组优化空间，也没法实现输出方案。

解决的方法是使用贪心来做这个题。我们先贪心地让每个?变成右括号，当变成右括号时没有左括号与之匹配时，存在两个解决方法：把当前位置变为左括号或把当前位置之前的某一个?调整为左括号。实际上这两个问题是同一个问题，从当前位置往前统计所有没变成左括号的?，并选择变为左括号产生的花费最少的一个转变即可。实现时维护一个存储?信息的堆即可选出最小值。

当最终仍然存在未匹配的左括号或需要左括号却无法产生时，即为无解的情况。另外统计价值之和时int会溢出要开long long。

可以这样思考贪心算法的正确性：在贪心的情境下，问题可以看做将?全替换为)，并从原来的?位置里选出一些改为(，并付出一定的花费，求花费最少的能将序列改为完全匹配序列的方案。这两个问题的答案是一致的，因为新问题可以看成原问题中，改成)的花费为0而改成(的花费为$a_i-b_i$后的问题，最小化后者同时也是最小化前者。每次从一个合法序列末尾放进一个)时，需要找一个(与之匹配，这个(要么已经存在，要么需要从)变过来，而变过来的时候上述方法实现了最小化。因此上述方法对新问题有正确性，对原问题也有正确性。

由于堆有每次$O(\log n)$的操作复杂度，算法总复杂度为$O(n \log n)$，且空间为$O(n)$，可以通过本题。

代码

// Code by KSkun, 2019/6
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

const int MAXN = 50005;

char s[MAXN];
int n, a[MAXN], b[MAXN];

struct Node {
    int no, a, b;
    bool operator<(const Node &rhs) const {
        return b - a < rhs.b - rhs.a;
    }
};

std::priority_queue<Node> pq;

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    int cnt = 0;
    LL sum = 0;
    for(int i = 1; i <= n; i++) {
        if(s[i] == '(') cnt++;
        if(s[i] == '?') {
            scanf("%d%d", &a[i], &b[i]);
            if(i == 1) {
                sum += a[i]; s[i] = '('; cnt++; continue;
            }
            sum += b[i]; s[i] = ')';
            pq.push(Node {i, a[i], b[i]});
        }
        if(s[i] == ')') {
            if(cnt == 0) {
                if(pq.empty()) {
                    puts("-1"); return 0;
                }
                Node t = pq.top(); pq.pop();
                if(t.no == n) {
                    t = pq.top(); pq.pop();
                }
                sum -= t.b; sum += t.a; s[t.no] = '(';
                if(t.no == i) cnt++; else cnt += 2;
            }
            if(s[i] == ')') cnt--;
        }
    }
    if(cnt != 0) {
        puts("-1"); return 0;
    }
    printf("%lld\n%s", sum, s + 1);
    return 0;
}