CF3D Least Cost Bracket Sequence

Luogu

CodeForces

算法

第一眼觉得是DP,但是推不出。

考虑括号问题的基本方法。用一个变量$sum$来维护,遇到(则加1,遇到)则减1。对于每一个?,我们可以先把它看作),同时sum--

若sum小于0,则说明没有足够的(来匹配,那么要将前面的一个?搞成(。因此去前面找一个?,如果找不到,那么不合法。

要使找到的?代价最小,就应该使得它的$-b+a$(即减掉)的,加上(的)最小。因此维护一个小根堆,按$-b+a$排序,每次碰到?就入堆,$sum<0$就出堆即可。

若最后$sum\neq 0$,那么也不合法。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

char c[50010];

struct node {
    int k,pos;
    bool operator <(const node& rhs) const {
        return k>rhs.k;
    }
};
priority_queue<node> Q;

mainint main() {
    scanf("%s",c+1); int l=strlen(c+1);
    int sum=0,ans=0;
    for (re int i=1;i<=l;i++) {
        if (c[i]=='?') {
            int a=read(),b=read();
            sum--,ans+=b,c[i]=')';
            Q.push((node){-b+a,i});
        }
        else if (c[i]=='(') sum++;
        else if (c[i]==')') sum--;
        if (sum<0) {
            if (Q.empty()) { printf("-1\n"); return 0; }
            node fr=Q.top(); Q.pop();
            sum+=2; ans+=fr.k; c[fr.pos]='(';
        }
    }
    if (sum) { printf("-1\n"); return 0; }
    printf("%I64d\n%s\n",ans,c+1);
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 08 PM

发表评论