What is the problem of finding the longest valid bracket sequence in POJ1141?

本文共计759个文字，预计阅读时间需要4分钟。

描述：让我们按以下方式定义一个正规括号序列：

空序列是一个正规序列。

如果 S 是一个正规序列，那么 (S) 和 [S] 也是正规序列。

如果 S 是一个正规序列，并且 S 的末尾是 ) 或 ]，那么 S+1 也是正规序列。

一个序列是正规的，当且仅当它满足上述条件。

(​​www.elijahqi.win/2017/12/28/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<cstdio>
#include<cstring>
int 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;l<n;++l){
for (int i=1;i+l<=n;++i){
int to=i+l,minn=dp[i][i]+dp[i+1][to];c[i][to]=i;
for (int j=i+1;j<to;++j)
if (minn>dp[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;
}