poj1141 Brackets Sequence

poj1141 Brackets Sequence

(​​ Description

Let us define a regular brackets sequence in the following way:

Empty sequence is a regular sequence.If S is a regular sequence, then (S) and [S] are both regular sequences.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

()[()]

Source Northeastern Europe 2001

我的dp 真的太菜啦qwq 只能从头好好学一学

题目要求求这个括号的最小匹配数 然后还需要输出方案 那么 设dp[i][j]表示i~j这个区间我最少需要填几个括号那么可以看出dp[i][j]=min(dp[i][k]+dp[k+1][j]) 枚举中间在哪里需要补括号即可c[i][j]表示i~j这个区间需要在c[i][j]这里分割一下 dp数组初始值给1 当c是-1的时候表示 这里不分割

如果我s[i]和s[j]正好 匹配的时候 dp[i][j] 可以考虑从dp[i+1][j-1]转移过来

输出的时候 l>r return

l==r直接输出对应的匹配 l

#include#includeint c[110][110],dp[110][110],n;char s[110];inline void print(int l,int r){ if (l>r) return; if (l==r){if (s[l]=='('||s[l]==')') printf("()");else printf("[]");return;} if (c[l][r]>0) print(l,c[l][r]),print(c[l][r]+1,r); else printf("%c",s[l]),print(l+1,r-1),printf("%c",s[r]);}int main(){ freopen("poj1141.in","r",stdin); scanf("%s",s+1);int n=strlen(s+1); memset(c,-1,sizeof(c));for (int i=1;i<=n;++i) dp[i][i]=1; for (int l=1;ldp[i][j]+dp[j+1][to]) minn=dp[i][j]+dp[j+1][to],c[i][to]=j; dp[i][to]=minn; if (s[i]=='('&&s[to]==')'||s[i]=='['&&s[to]==']') if (dp[i][to]>dp[i+1][to-1]) dp[i][to]=dp[i+1][to-1],c[i][to]=-1; } }print(1,n);printf("\n"); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。