首页 > 代码库 > codevs 3657 括号序列

codevs 3657 括号序列

2024-09-16 17:29:11   207人阅读

时间限制: 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个字符)。



区间dp
屠龙宝刀点击就送
#include <cstring>#include <cstdio>int dp[150][150];char str[150];int min(int a,int b){    return a>b?b:a;}int main(){    scanf("%s",str);    int l=strlen(str);    for(int i=1;i<=l;i++) dp[i][i]=1;    for(int i=2;i<=l;i++)    {        for(int j=1;j<=l-i+1;j++)        {            int jj=i+j-1;dp[j][jj]=0x7fffffff;            if((str[j-1]==‘(‘&&str[jj-1]==‘)‘)||(str[j-1]==‘[‘&&str[jj-1]==‘]‘)) dp[j][jj]=dp[j+1][jj-1];            for(int k=j;k<jj;k++) dp[j][jj]=min(dp[j][jj],dp[j][k]+dp[k+1][jj]);        }    }    printf("%d",dp[1][l]);    return 0;}
 
 
codevs 3657 括号序列






























        

            
                
                  
                
                

                    联系

                    我们