括号序列
题⽬描述
  定义如下规则序列(字符串)：
    1．空序列是规则序列；
    2．如果S是规则序列，那么(S)和[S]也是规则序列；
    3．如果A和B都是规则序列，那么AB也是规则序列。
  例如，下⾯的字符串都是规则序列：
    ()，[]，(())，([])，()[]，()[()]
  ⽽以下⼏个则不是：
    (，[，]，)(，())，([()
  现在，给你⼀些由‘(’，‘)’，‘[’，‘]’构成的序列，你要做的，是出⼀个最短规则序列，使得给你的那个序
列是你给出的规则序列的⼦列。(对于序列a1，a2，…，an和序列bl，b2，…，bm，如果存在⼀组下标1≤i1<i2<…<in≤m，使得aj＝b(i,j)对⼀切1≤j≤n成⽴，那么a1，a2…，an就叫做b1，b2，…，bm的⼦列。
输⼊输出格式
  输⼊格式：
    输⼊⽂件仅⼀⾏，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，长度不超过100。
  输出格式：
    输出⽂件也仅有⼀⾏，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，把你到的规则序列输出即可。因为规则序列可能不⽌⼀个，因此要求输出的规则序列中嵌套的层数尽可能地少。
输⼊输出样例
  输⼊样例#1：
  ([()
  输出样例#1：
  ()[]()
说明
  输出解释：
  {最多的嵌套层数为1，如层数为2时的⼀种为()[()]}
jsoi2011
【题⽬分析】
说⼀下⼤体思路，dp[i][j]表⽰从i到j需要插⼊的括号的个数，path[i][j]记录i到j中划分位置k，递归输出
⾮满分算法
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1100;
char str[maxn];
int dp[maxn][maxn],p[maxn][maxn],len;
void print(int start,int end)
{
if(start>end)
return ;
else if(start==end)//到没有被匹配的括号
{
if(str[start]=='('||str[end]==')')
printf("()");
else
printf("[]");
}
else if(p[start][end]==-1)//如果这段括号中没有被分割的位置    {字符串长度规则
printf("%c",str[start]);
print(start+1,end-1);
printf("%c",str[end]);
}
else//从p[start][end]处被分开，递归输出
{
print(start,p[start][end]);
print(p[start][end]+1,end);
}
}
int main()
{
memset(dp,0,sizeof dp);
scanf("%s",str+1);
len=strlen(str+1);
for(int i=1;i<=len;i++)
dp[i][i]=1;
for(int l=2;l<=len;l++)
for(int i=1;i<=len-1;i++)
{
int j=i+l-1;
if(str[i]=='('&&str[j]==')'||str[i]=='['&&str[j]==']')
dp[i][j]=dp[i+1][j-1],
p[i][j]=-1;
else dp[i][j]=0x7fffffff;
for(int k=i;k<=j-1;k++)
if(dp[i][j]>dp[i][k]+dp[k][j])
dp[i][j]=dp[i][k]+dp[k][j],
p[i][j]=k;
}
print(1,len);
return0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。