Codeforces：Least Cost Bracket Sequence

Codeforces：Least Cost Bracket Sequence

题目链接：http://codeforces.com/contest/3/problem/D

题目大意：给出一个仅包含'('，')'，'?'的字符串，现要求将所有'?'替换成'('或')'使得所有括号匹配，将第i个'?'换成'('的代价为a_i，换成')'的代价为b_i，问最小代价.

贪心

拿到题目自然而然想到动态规划的做法，然而其复杂度O（n²）不满足题意.

我们发现当i<j，若子字符串substr（1，i）不满足匹配，则substr（1，j）不满足匹配.

故可以考虑先将s中所有'?'替换成')'，得到一个仅含'('和')'的字符串s'.

然后从左边开始检查substr（1，i）是否满足匹配，若不满足匹配则将{s'[x]|1≤x≤i且s[x]='?'}中任意一个替换成'('即可使substr（1，i）重新满足匹配.

选择priority_queue维护代价min{value[x]|1≤x≤i且s[x]='?'}，时间复杂度为O（nlgn）

/*strlen（char *s）的复杂度为O（n）*/

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #define N 50005
 6 using namespace std;
 7 char s[N];
 8 int a[N][2],m,num,k,f[N],len;
 9 bool Left[N],flag=1;
10 struct node{
11     int id,v;
12     node(int _id=-1,int _v=-1){
13         id=_id;v=_v;
14     }
15     friend bool operator < (node a,node b){
16         return a.v<b.v;
17     }
18 };
19 priority_queue<node>q;
20 int main(void){
21     scanf("%s",s);
22     len=strlen(s);
23     for(int i=0;i<len;++i)
24         if(s[i]=='?')f[i]=m++;
25     for(int i=0;i<m;++i)
26         scanf("%d%d",&a[i][0],&a[i][1]);
27     for(int i=0;i<len;++i){
28         if(s[i]=='(')num++;
29         else if(s[i]==')')num--;
30         else if(s[i]=='?'){
31             num--;
32             q.push(node(i,a[f[i]][1]-a[f[i]][0]));
33         }
34         if(num<0){
35             if(q.empty()){
36                 flag=0;
37                 break;
38             }else{
39                 node t=q.top();q.pop();
40                 Left[t.id]=1;
41                 num+=2;
42             }
43         }
44     }
45     if(flag&&num==0){
46         long long ans=0;
47         for(int i=0;i<len;++i){
48             if(s[i]=='?'){
49                 if(Left[i]){
50                     ans+=a[f[i]][0];
51                     s[i]='(';
52                 }else{
53                     ans+=a[f[i]][1];
54                     s[i]=')';
55                 }
56             }
57         }
58         printf("%I64d
%s",ans,s);
59     }else printf("-1");
60 }

/*若在

q.push(node(i,a[f[i]][1]-a[f[i]][0]));

前添加

string test;

则会出现segmentation fault，没有发现相关资料。

ac后上stackoverflow提问，结果复现不出来了:(