本文共 2972 字，大约阅读时间需要 9 分钟。

(??)1 22 8

4()()

题意：

是给一个序列，序列里面会有左括号、问号、右括号。对于一个‘？’而言，可以将其替换为一个‘（’，也可以替换成一个‘）’，但是都有相应的代价。

问：如何替换使得代价最小。前提是替换之后的序列中，括号是匹配的。如果不能替换为一个括号匹配的序列则输出-1。

题解：

刚开始想的是动态规划，但是想想这个好像是有后效的，所以动态规划就作罢了。

然后就贪心吧。先假设所有的‘？’全部替换成右括号，然后按常规的办法去检测这个序列是否括号匹配。

所谓的常规的办法就是遍历这个序列，维护一个计数器cnt，当遇到左括号时计数器+1，遇到右括号时计数器-1

如果中途遇到cnt小于0的情况，则说明这个序列不是括号匹配的，但是在我们这里，右括号可能是‘？’变来的，所以当遇到cnt小于0时，则去看前面有没有‘？’变过来的右括号，如果没有，那就说明无论如何这个序列无法被替换为括号匹配的序列；如果有的话，则选取一个“最好”的由‘？’变过来的右括号，将其改为左括号，这样的话cnt又可以加2了。这里所谓的“最好”，就是贪心的过程。至于怎样的最好，就自己去想吧。

如果这样到最后cnt还大于0，则说明即使无法获得一个括号匹配的序列，输出-1即可。

1.将所有的问号替换为右括号

2.遍历序列，维护计数器

3.当遇到计数器小于0则考虑从前面找一个问号变成左括号而不是右括号

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define rep(i,a,n) for (int i=a;i
          
           =a;i--)#define pb push_back#define fi first#define se secondtypedef vector
           
             VI;typedef long long ll;typedef pair
            
              PII;const int maxn=1e6+100;struct node{ int v,p; bool operator <(const node& b)const{ return v
             
               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;}
             
            
           
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/fouzhe/article/details/56022900 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！