【基础练习】【区间DP】codevs3657 括号序列题解

落日映苍穹つ 2022-08-03 14:56 160阅读 0赞

题目描述 Description

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

（1）空序列是合法的

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

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

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

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

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

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

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

([()

样例输出 Sample Output

最后一次把不合法的S变为合法的之前可能情况：  
1）S形如（S′）或\[S′\]：  
   只需把S′变合法即可。  
   f\[i,j\]= f\[i+1,j-1\]  
2）S形如（S′ 或\[S′：  
   先把S′变为合法的，右边加 ）或\]即可。  
   f\[i,j\]= f\[i+1,j\]+1

3）S形如   S′）或S′\]：  
   先把S′化为合法的，左边加（或 \[即可。  
   f\[i,j\]= f\[i,j-1\]+1  
4）把长度大于1的序列SiSi+1…..Sj-1Sj分为两部分:  
   Si...... Sk，Sk+1….. Sj  
   分别化为规则序列.  
   则：f\[i,j\]=f\[i,k\]+f\[k+1,j\] ；i<=k<=j-1;  
上述4种情况取最小值即可。

代码如下：

//codevs3657 括号序列 区间DP
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=100+10;
    const int maxint=0x3f3f3f3f;
    char s[100+10];
    int f[maxn][maxn];
    
    int main()
    {
        scanf("%s",s);
        int n=strlen(s);
        for (int i=0;i

`——宣父犹能畏后生，丈夫未可轻年少。`