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.

The first line contains a non-empty pattern of even length, consisting of characters "(", ")" and "?". Its length doesn't exceed 5·104. 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?≤?106), 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 22 8output
4()()
參考博客鏈接
題意：
是給一個(gè)序列，序列里面會有左括號、問號、右括號。對于一個(gè)‘？’而言，可以將其替換為一個(gè)‘（’，也可以替換成一個(gè)‘）’，但是都有相應(yīng)的代價(jià)。
問：如何替換使得代價(jià)最小。前提是替換之后的序列中，括號是匹配的。如果不能替換為一個(gè)括號匹配的序列則輸出-1。
題解：
剛開始想的是動態(tài)規(guī)劃，但是想想這個(gè)好像是有后效的，所以動態(tài)規(guī)劃就作罷了。
然后就貪心吧。先假設(shè)所有的‘？’全部替換成右括號，然后按常規(guī)的辦法去檢測這個(gè)序列是否括號匹配。
所謂的常規(guī)的辦法就是遍歷這個(gè)序列，維護(hù)一個(gè)計(jì)數(shù)器cnt，當(dāng)遇到左括號時(shí)計(jì)數(shù)器+1，遇到右括號時(shí)計(jì)數(shù)器-1
如果中途遇到cnt小于0的情況，則說明這個(gè)序列不是括號匹配的，但是在我們這里，右括號可能是‘？’變來的，所以當(dāng)遇到cnt小于0時(shí)，則去看前面有沒有‘？’變過來的右括號，如果沒有，那就說明無論如何這個(gè)序列無法被替換為括號匹配的序列；如果有的話，則選取一個(gè)“最好”的由‘？’變過來的右括號，將其改為左括號，這樣的話cnt又可以加2了。這里所謂的“最好”，就是貪心的過程。至于怎樣的最好，就自己去想吧。
如果這樣到最后cnt還大于0，則說明即使無法獲得一個(gè)括號匹配的序列，輸出-1即可。
1.將所有的問號替換為右括號
2.遍歷序列，維護(hù)計(jì)數(shù)器
3.當(dāng)遇到計(jì)數(shù)器小于0則考慮從前面找一個(gè)問號變成左括號而不是右括號
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int maxn=1e6+100;struct node{    int v,p;    bool Operator <(const node& b)const{        return v<b.v;    }    node(int x=0,int y=0):v(x),p(y) {}};priority_queue<node> q;char s[maxn];int main(){    scanf("%s",s+1);    int l=(int)strlen(s+1);    int cnt=0;    ll ans=0;    rep(i,1,l+1)    {        if(s[i]=='?')        {            int a,b;            scanf("%d%d",&a,&b);            ans+=b;            if(cnt>0)                q.push(node(b-a,i)),cnt--,s[i]=')';            else            {                q.push(node(b-a,i));                cnt--;                s[i]=')';                while(cnt<0)                {                    if(q.empty())                    {                        puts("-1");                        return 0;                    }                    node t=q.top();                    q.pop();                    ans-=t.v;                    s[t.p]='(';                    cnt+=2;                                    }            }        }        else if(s[i]=='(') cnt++;        else if(s[i]==')')        {            cnt--;            while(cnt<0)            {                if(q.empty())                {                    puts("-1");                    return 0;                }                node t=q.top();                q.pop();                ans-=t.v;                s[t.p]='(';                cnt+=2;            }        }    }    if(cnt) puts("-1");    else    {        printf("%lld/n",ans);        printf("%s/n",s+1);    }    return 0;}