括号序列【问题描述】       定义如下规则序列(字符串)： 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，…， 的子列。【输入】       输入文件仅一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，长度不超过100。【输出】       输出文件也仅有一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。【样例】 bracket.in([() bracket.out()[]()                          {最多的嵌套层数为1，如层数为2时的一种为()[()]}     【算法分析】    对于输入的括号序列字符串，从左向右进行查找，用一个数组来记录查找配对的情况，如果一个括号有相应的括号跟它对应，则将它标记为0，如果没有相应的括号跟它对应，则保存原子始代码的编号，“[]”分别为-1和1，“()”分别为-2和2。    因此对于读入的字符串，首先将其转换为相应的代码存放到数组里，为后面查找匹配做准备。    查找匹配时，可用这样的方法：    如果当前的字符是右括号，则跟前面的一个没有匹配的左括号对照，看是否匹配，如果匹配，则将两个字符标记为0，查找并定位到左边的第一个没有匹配的左括号(如果有的话)。如果当前的字符是左括号，则记住这个不匹配的左括号的位置，为后面找到右括号时匹配做准备。    从第一个字符开始到最后一个字符重复上面的过程，检查处理完毕。 输出时考虑到不增加嵌套的层数，以就近的原则，将出现不匹配的一个括号时，输出两个匹配的括号。         括号序列 题解然后进行DP。设f[i,j]=简化后字符串中第i个字符至第j个字符构成的子串需要添加的括号数。 当i>j时我们规定f[i,j]=0。 当i=j时显然有f[i,j]=1。 当i<j时，我们可以把这个字符串分为两段分别处理，因此f[i,j]为所有f[i,k]+f[k+1,j]中的最小值，这里i<=k<j。另外，如果第i个字符和第j个字符恰好配对，那么可以就让它们配对，即f[i,j]还可以等于f[i+1,j-1]。可以用记忆化搜索实现.         #include<iostream>#include<string>using namespace std; string s="00";int min(int a,int b){ return (a<b? a:b);}int bracket(int i,int j){ int answer=0; if(i>j)  return 0; else if(i==j)  return 1; else{  if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']'))   answer=min(answer,bracket(i+1,j-1));  if(s[i]=='('||s[i]=='[')   answer=min(answer,bracket(i+1,j)+1);  if(s[i]==')'||s[i]==']')   answer=min(answer,bracket(i,j-1)+1);  for(int k=i;i<j;)  {   answer=min(answer,bracket(i,k)+bracket(k+1,j));  } } return answer;} void main(){ cin>>s; int i=0,j=s.length(); cout<<bracket(i,j)<<endl;}   为什么输出不了啊？？？？ 寻求高手帮忙~~~~ 感谢了a

评论