| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 29502 | Accepted: 8402 | Special Judge | ||
Description
1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. If A and B are regular sequences, then AB is a regular sequence.
For example, all of the following sequences of characters are regular brackets sequences:
(), [], (()), ([]), ()[], ()[()]
And all of the following character sequences are not:
(, [, ), )(, ([)], ([(]
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n.
Input
Output
Sample Input
([(]
Sample Output
()[()]
Source
题目大意: 给你一贯括号序列(只包含小括号和中括号)，让你找出长度最小的regular brackets sequence包含此子序列.其中的regular brackets sequence定义如下:
1)空序列是一个regular brackets sequence;
2)如果s是一个regular brackets sequence,那么[s] 也是一个regular brackets sequence,(s)也是一个regular brackets sequence.
3)如果A,B都是regular brackets sequence,那么AB也是一个regular brackets sequence.
例如:()、[]、()[] 、([]) 、([])()[()]都是regular brackets sequence。
而[[[、 (((((、 ([)] 则都不是regular brackets sequence。其中以“([)]”为例，包含它最小的regular brackets sequence有两个:()[()]或者是([])[].而你只要输出其中一个就行。
//f[i][j]表示区间i~j内需要最少的字符数能够匹配，path[i][j]表示到达该状态是哪种情况，
// -1表示第一个和最后一个，其他表示中间的分段点，然后递归输出(递归改变次序)
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1010
char s[N];
int f[N][N],path[N][N];
void out(int l,int r){
if(l>r) return ;
if(l==r){//到达了最后
if(s[l]=='('||s[l]==')')
printf("()");
else
printf("[]");
return ;
}
if(path[l][r]==-){//首尾，先输出开始，然后递归输出中间，最后输出结尾
putchar(s[l]);
out(l+,r-);
putchar(s[r]);
}
else{
out(l,path[l][r]);
out(path[l][r]+,r);
}
}
int main(){
while(gets(s+)){//有空串，scanf("%s"),不能读空串，然后少一个回车，会出错
int n=strlen(s+);
for(int i=;i<=n;i++) f[i][i]=;//一个的话只需一个就可以匹配
for(int x=;x<n;x++){//枚举区间长度
for(int i=;i<=n-x;i++){//枚举区间开始位置
int j=i+x;
f[i][j]=0x3f3f3f3f;
if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')){
if(f[i+][j-]<f[i][j]){
f[i][j]=f[i+][j-];path[i][j]=-;
}
}
for(int k=i;k<j;k++){//中间分隔情况
if(f[i][k]+f[k+][j]<f[i][j]){
f[i][j]=f[i][k]+f[k+][j];path[i][j]=k;
}
}
}
}
out(,n);
putchar('\n');
}
return ;
}
//update 2.0
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=;
int n,f[N][N];char s[N];
bool match(char a,char b){
if(a=='('&&b==')') return ;
if(a=='['&&b==']') return ;
return ;
}
void print(int i,int j){
if(i>j) return ;
if(i==j){
if(s[i]=='('||s[i]==')') printf("()");
else printf("[]");
return ;
}
int ans=f[i][j];
if(match(s[i],s[j])&&ans==f[i+][j-]){
printf("%c",s[i]);
print(i+,j-);
printf("%c",s[j]);
return ;
}
for(int k=i;k<j;k++){
if(ans==f[i][k]+f[k+][j]){
print(i,k);
print(k+,j);
return ;
}
}
}
int main(){
while(gets(s+)){
n=strlen(s+);
memset(f,0x3f3f3f3f,sizeof f);
for(int i=;i<=n;i++){
f[i+][i]=;
f[i][i]=;
}
for(int i=n-;i>=;i--){
for(int j=i+;j<=n;j++){
f[i][j]=n;
if(match(s[i],s[j])) f[i][j]=min(f[i][j],f[i+][j-]);
for(int k=i;k<j;k++){
f[i][j]=min(f[i][j],f[i][k]+f[k+][j]);
}
}
}
//printf("%d\n",f[1][n]);
print(,n);
putchar('\n');
}
return ;
}