Brackets Sequence
| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 24949 | Accepted: 7018 | Special Judge | ||
Description
Let us define a regular brackets sequence in the following way:
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.
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
The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.
Output
Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.
Sample Input
([(]
Brackets Sequence
| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 24949 | Accepted: 7018 | Special Judge | ||
Description
Let us define a regular brackets sequence in the following way:
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.
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
The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.
Output
Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.
Sample Input
([(]
Sample Output
()[()]题目大意.
给出一组括号，添加最少的括号个数使其完全匹配.
1.空串是匹配的
2.如果s是匹配的，那(s),[s]是匹配的.
3.如果a匹配，b匹配.那ab是匹配的.
注意:输入数据只有一个，且可能有多余空格（用gets()读取就好了）.
4.输出注意是有换行的（这和其他题目类似）
我的想法.
1.将原题的匹配问题看成是,从0，到n-1的匹配.问题的定义是从l到r的匹配.dp[l][r]
2.只有一个字符（l==r）是一定不匹配的,(当匹配后,一定是输出() 或者 [] )
3.如果l<r；那麽dp[l][r]=min(dp[l][k]+dp[k+1][r]);但是要处理直接有l于r匹配的情况.否则无限递归.
具体如下.
<pre name="code" class="cpp"> /*Source Code
Problem: 1141 User:
Memory: 8188K Time: 94MS
Language: GCC Result: Accepted
Source Code*/
#include <stdio.h>
#include <string.h>
#define maxn 1001 //开大了哈
#define maxv ( (1 << 30) -1 )
int dp[maxn][maxn]={-1};
int path[maxn][maxn]={-1};
int p[maxn]={0};
int min(int x,int y){
return x<y?x:y;
}
int isMatch(char left,char right){
if((left=='('&&right==')')||(left=='['&&right==']'))
return 1;
else
return 0;
}
int Match(char str[],int l,int r){
if(l>r) return 0;
if(dp[l][r]!=-1) return dp[l][r]; //计算过的
if(l==r){ //一定会添加一个
return (dp[l][r]=1);
}else{
int k;
int m=maxv;
if(isMatch(str[l],str[r])){ //如果可以匹配先记录当前匹配的个数
m=Match(str,l+1,r-1);
path[l][r]=-2; //嫖妓l,r的匹配为直接匹配.
}
for(k=l;k+1<=r;k++){
if(m==maxv||(m>Match(str,l,k)+Match(str,k+1,r))){ //没有计算或者，存在分为两段的更好方法.
m=Match(str,l,k)+Match(str,k+1,r);
path[l][r]=k; //记录l,r，是经过分为l,path[l][k], 和 path[l][k]+1到r这样分割的.
}
}
return dp[l][r]=m;
}
}
void print(char str[],int l,int r){
if(l>r) return;
else if(l==r){
if(str[l]==')') printf("(%c",str[l]);
if(str[l]==']') printf("[%c",str[l]);
if(str[l]=='(') printf("%c)",str[l]);
if(str[l]=='[') printf("%c]",str[l]);
}else{
if(path[l][r]==-2){
printf("%c",str[l]);
print(str,l+1,r-1);
printf("%c",str[r]);
}else{
print(str,l,path[l][r]);
print(str,path[l][r]+1,r);
}
}
}
int main(){
char str[maxn]="";
int l=0,r,m=maxv;
int i;
memset(dp,-1,sizeof(dp));
memset(path,-1,sizeof(path));
if (gets(str) == NULL)
return 0;
r=strlen(str)-1;
Match(str,l,r);
print(str,l,r);
printf("\n");
return 0;
}