codevs——T3657 括号序列-白红宇

codevs——T3657 括号序列

阅读量：4948 次

发布时间：2019-06-11

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

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 黄金 Gold

题目描述

Description

我们用以下规则定义一个合法的括号序列：

（1）空序列是合法的

（2）假如S是一个合法的序列，则 (S) 和[S]都是合法的

（3）假如A 和 B 都是合法的，那么AB和BA也是合法的

例如以下是合法的括号序列：

(), [], (()), ([]), ()[], ()[()]

以下是不合法括号序列的：

(, [, ], )(, ([]), ([()

现在给定一些由'(', ')', '[', ，']'构成的序列，请添加尽量少的括号，得到一个合法的括号序列。

输入描述

Input Description

输入包括号序列S。含最多100个字符（四种字符： '(', ')', '[' and ']') ，都放在一行，中间没有其他多余字符。

输出描述

Output Description

使括号序列S成为合法序列需要添加最少的括号数量。

样例输入

Sample Input

([()

样例输出

Sample Output

数据范围及提示

Data Size & Hint

【样例说明】最少添加2个括号可以得到合法的序列：()[()]或([()])【数据范围】S的长度<=100 (最多100个字符)。

1 #include 
          
            2 #include 
           
             3 #include 
            
              4 #include 
             
               5 #include 
              
                6  7 using namespace std; 8  9 string s;10 int f[10015][10015];11 12 int main()13 {14     cin>>s;15     int len=s.size();16     for(int i=1;i<=len;i++) f[i][i]=1;17     for(int l=2;l<=len;l++)18         for(int i=1;i<=len-l+1;i++)19         {20             int j=l+i-1;21             f[i][j]=1e7;22             if((s[i-1]=='('&&s[j-1]==')')||(s[i-1]=='['&&s[j-1]==']'))23                 f[i][j]=f[i+1][j-1];24             for(int k=i;k