括号序列
【问题描述】
       定义如下规则序列(字符串)：

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

评论