codevs——T3657 括号序列

时间：2023-03-09 03:46:41
codevs——T3657 括号序列
 时间限制: 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
2
数据范围及提示 Data Size & Hint
【样例说明】

最少添加2个括号可以得到合法的序列：()[()]或([()])

【数据范围】

S的长度<=100 (最多100个字符)。

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <cstdio>

 using namespace std;

 string s;

 int f[][];

 int main()

 {

     cin>>s;

     int len=s.size();

     for(int i=;i<=len;i++) f[i][i]=;

     for(int l=;l<=len;l++)

         for(int i=;i<=len-l+;i++)

         {

             int j=l+i-;

             f[i][j]=1e7;

             if((s[i-]=='('&&s[j-]==')')||(s[i-]=='['&&s[j-]==']'))

                 f[i][j]=f[i+][j-];

             for(int k=i;k<j;k++)

                 f[i][j]=min(f[i][j],f[i][k]+f[k+][j]);

         }

     printf("%d",f[][len]);

     return ;

 }

相关文章