UVa 1662 Brackets Removal-白红宇

UVa 1662 Brackets Removal

阅读量：4659 次

发布时间：2019-06-09

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

题意：

给出一个序列，判断序列中哪些括号是可以去掉的，只可以改变符号。输出括号最少的序列。

思路：

感觉这道题目就是写起来繁琐了点，我的代码比较啰嗦..

先保存每对括号的左右坐标，然后对于每一对括号，我们去寻找它前面和后面的符号，如果前后有乘除号并且括号内有加减号，那么这括号肯定是不能去掉的。另外的情况下都是可以去掉括号的，当然了，如果前面是减号或者是除号，有些符号需要相应的改变。

还有要注意一点，很重要！！

就是如果有对括号是不能去掉的，那么对于括号内的符号，我们需要标记一下。这样当我们考虑在它外面的大括号时，就不去考虑它里面的情况。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
               10 #include
               11 using namespace std; 12 typedef long long ll; 13 typedef pair
               
                 pll; 14 const int INF=0x3f3f3f3f3f; 15 const int maxn=10000+5; 16 17 int cnt; 18 int len; 19 char str[maxn]; 20 int vis[maxn]; 21 22 struct node 23 { 24 int l,r; 25 int d; 26 bool operator<(const node& rhs) const 27 { 28 return d

sp; 61 memset(vis,0,sizeof(vis)); 62 63 len=strlen(str+1); 64 for(int i=1;i<=len;i++) 65 { 66 if(str[i]=='(') sp.push(i); 67 else if(str[i]==')') 68 { 69 int x=sp.top(); sp.pop(); 70 a[cnt].l=x; 71 a[cnt].r=i; 72 a[cnt].d=i-x; 73 cnt++; 74 } 75 } 76 77 sort(a,a+cnt); 78 /* 79 for(int i=0;i

转载于:https://www.cnblogs.com/zyb993963526/p/6934284.html

你可能感兴趣的文章