游客 注册 | 登录
中文 | En

3757 - 括号序列

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

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

（1）空序列是合法的

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

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

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

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

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

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

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

题目输入

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

题目输出

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

输入/输出样例

输入格式

([()

输出格式

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

C++解答

//AUTHOR::STDAFX
//ALGORITHM::DP
 
#define MAXN 350UL
#define INF 0X3fffffff
 
#include <cstdio>
#include <cstring>
 
using namespace std;
 
bool check(char,char);
 
char input[MAXN];
int n,del,f[MAXN][MAXN],tp;
 
int main(){
    //freopen("t.txt","r",stdin);
    //freopen("","w",stdout);
    scanf("%s",input);
    n=strlen(input);
    for(int i=0;i<n;i++){
        f[i][i]=1;
    }
    for(int i=2;i<=n;i++){
        for(int j=0;j<=n-i;j++){
            tp=j+i-1;
            if(check(input[j],input[tp])){
                f[j][tp]=f[j+1][tp-1];
            }
            else{
            	f[j][tp]=INF;
			}
            for(int k=j;k<tp;k++){
                if(f[j][tp]>f[j][k]+f[k+1][tp]){
                    f[j][tp]=f[j][k]+f[k+1][tp];
                }
            }
        }
    }
    printf("%d",f[0][n-1]);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
 
bool check(char a,char b){
    if((a=='('&&b==')')||(a=='['&&b==']')){
        return true;
    }
    return false;
}
请先登陆