首页 > 代码库 > 括号序列的最小代价

括号序列的最小代价

题意

查看原题

这里有一个关于合法的括号序列的问题。

如果插入“+”和“1”到一个括号序列,我们能得到一个正确的数学表达式,我们就认为这个括号序列是合法的。例如,序列"(())()", "()"和"(()(()))"是合法的,但是")(", "(()"和"(()))("是不合法的。我们这有一种仅由“(”,“)”和“?”组成的括号序列,你必须将“?”替换成括号,从而得到一个合法的括号序列。

对于每个“?”,将它替换成“(”和“)”的代价已经给出,在所有可能的变化中,你需要选择最小的代价。

Input
第一行是一个非空的偶数长度的字符串,它仅由“(”,“)”和“?”组成。它的长度不大于 50000。接着是m行,m是字符串中“?”的个数。每一行包含两个整数 ai和bi ( 1<=ai,bi<=1000000), ai是将第i个“?”替换成左括号的代价, bi是将第i个“?”替换成右括号的代价。
Output
在一行中输出合法的括号序列的最小代价。
如果没有答案,输出-1。
Input示例
(??)
1 2
2 8
Output示例
4

思路

刚开始把?全部用)替换。然后记录一下标记前缀和s,(标记为+1,)标记为-1。如果遇到某个时候s<0,那么就把之前的?里面里从右括号变成左括号需要的费用最少的改成(。并s+=2。这一步可以用优先队列来维护。

 

 1 #include <map>
 2 #include <set>
 3 #include <cmath>
 4 #include <ctime>
 5 #include <stack>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <cctype>
 9 #include <bitset>
10 #include <string>
11 #include <vector>
12 #include <cstring>
13 #include <iostream>
14 #include <algorithm>
15 #include <functional>
16 #define fuck(x) cout<<"["<<x<<"]";
17 #define FIN freopen("input.txt","r",stdin);
18 #define FOUT freopen("output.txt","w+",stdout);
19 //#pragma comment(linker, "/STACK:102400000,102400000")
20 using namespace std;
21 typedef long long LL;
22 typedef pair<int, int> PII;
23 typedef long long LL;
24 
25 const int MX = 5e4 + 5;
26 
27 char S[MX];
28 int L[MX], R[MX];
29 
30 int main() {
31     //FIN;
32     scanf("%s", S);
33     int n = strlen(S);
34 
35     priority_queue<int> Q;
36     LL sum = 0; bool ok = true;
37     for(int i = 0; i < n; i++) {
38         if(S[i] == ?) {
39             scanf("%d%d", &L[i], &R[i]);
40             sum += R[i];
41         }
42     }
43 
44     int now = 0;
45     for(int i = 0; i < n; i++) {
46         if(S[i] == () now++;
47         else if(S[i] == ) || S[i] == ?) now--;
48         if(S[i] == ?) Q.push(R[i] - L[i]);
49         if(now < 0) {
50             if(Q.empty()) {
51                 ok = false; break;
52             }
53             sum -= Q.top(); Q.pop(); now += 2;
54         }
55     }
56     if(now != 0) ok = false;
57     printf("%I64d\n", ok ? sum : -1);
58     return 0;
59 }

 

【REFERENCE】

优先队列+括号配对 51Nod1476 括号序列的最小代价

括号序列的最小代价