CF3D Least Cost Bracket Sequence 题解

CF3D

题意

一个括号序列，其中有几位为 ?，将第 /(i/) 个 ? 修改为 ( 的代价是 /(a_i/)，修改为 ) 的代价是 /(b_i/)，问将所有 ? 修改后使得序列匹配的最小代价。

分析

贪心。发现一个匹配的括号序列的每一个前缀的左括号数一定不小于右括号数，因此先把问号都替换成右括号，对于每一位判断一下，如果到这一位时右括号数大于左括号数，就把前面右换左代价最小的一位替换成左。这样一定是正确的，因为前面如果左括号多了后面还能补救，但是右括号多了前面就不能完全匹配了。

于是可以从前往后扫，遇到一个问号就换成右括号，并把这个位置的下标和右换左的代价一起扔到一个小根堆里，如果右括号多了就取出堆顶换成左括号。

核心代码

priority_queue<Pair,vector<Pair>,greater<Pair> >q;
signed main(){
    scanf("%s",s+1);n=strlen(s+1);int i,j,cnt=0;
    for(i=1;i<=n;i++) if(s[i]=='?') m++,mp[i]=++mp[0];for(i=1;i<=m;i++) qread(a[i],b[i]);
    for(i=1;i<=n;i++){
        if(s[i]=='(') cnt++,t[i]=s[i];if(s[i]==')') cnt--,t[i]=s[i];
        if(s[i]=='?'){
            t[i]=')';q.push(Pair(a[mp[i]]-b[mp[i]],i));cnt--;ans+=b[mp[i]];
        }if(cnt<0){
            if(q.empty()) return printf("-1/n"),0;
            auto u=q.top();q.pop();t[u.second]='(';cnt+=2;
            // cout<<u.first<<" "<<u.second<<endl;
            ans+=u.first;
        }
    }if(cnt) return printf("-1/n"),0;
    printf("%lld/n%s/n",ans,t+1);
    return 0;
}