定义如下规则序列(字符串)：
1．空序列是规则序列；
2．如果S是规则序列，那么(S)和[S]也是规则序列；
3．如果A和B都是规则序列，那么AB也是规则序列。
       例如，下面的字符串都是规则序列：
()，[]，(())，([])，()[]，()[()]
       而以下几个则不是：
(，[，]，)(，())，([()
现在，给你一些由‘(’，‘)’，‘[’，‘]’构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列。(对于序列a1，a2，…， 和序列bl，b2，…， ，如果存在一组下标1≤i1<i2<…< ≤m，使得aj＝ 对一切1≤j≤n成立，那么a1，a2…， 就叫做b1，b2，…， 的子列。

输入文件仅一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，长度不超过255。

添加括号最少的数目

输入

[[(([]

输出

4

ACM/ICPC 2001

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

using namespace std;

int n,f[][];

char a[];

int main(){

    scanf("%s",a+);

    a[] = '!';

    n = strlen(a) - ;

    for(int i = ;i <= n;i++){

        for(int j = ;j <= n;j++){

            f[i][j] = ;

            if(j == i - ) f[i][j] = ;

            if(i == j) f[i][j] = ;

        }

    }

    for(int l = ;l <= n;l++){

        for(int i = ;i <= n - l + ;i++){

            int j = i + l - ;

            if((a[i] == '(' && a[j] == ')') || (a[i] == '[' && a[j] == ']')) f[i][j] = min(f[i][j],f[i+][j-]);

            if(a[i] == '(' || a[i] == '[') f[i][j] = min(f[i][j],f[i+][j] + );

            if(a[j] == ')' || a[j] == ']') f[i][j] = min(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]);

        }

    }

    cout<<f[][n];

    return ;

}