Monday, February 19, 2018

[POJ]1141 Brackets Sequence


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.

思路和POJ 2955是类似的。我们用DP[i][j]表示把子串s[i, j]补完成合法序列所需要的最少的字符数。我们有递推公式:

  • DP[i][j] = D[i + 1][j],如果s[i]在s[i + 1, j]中没有括号与之match
  • DP[i][j] = max(dp[i + 1][k - 1] + dp[k + 1][j]),如果s[i]和s[k]match
但是这个公式只能算出最少需要补完多少个字符来使之合法。我们还需要记录打印结果的路径(只打印满足条件的一个即可),我们用path[i][j]来记录s[i,j]的分割点,如果s[i]没有match,path[i][j] = -1;如果s[i]和s[k]match且其使得需要补完的char数最少,path[i][j] = k。我们打印的时候根据path自上而下递归地打印即可,详细可以参见代码中的print方法。时间复杂度空间复杂度均为O(n^2),代码如下:

//POJ 1141
/*
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.
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.
*/
#include <cstdio>
#include <cstring>
const int MAX = 105;
int dp[MAX][MAX], path[MAX][MAX];
char s[MAX];
void print(int i, int j)
{
if(i > j)return;
if(i == j)
{
if(s[i] == '(' || s[i] == ')')printf("()");
else printf("[]");
return;
}
if(path[i][j] == -1)
{
print(i, i);
print(i + 1, j);
}
else
{
int k = path[i][j];
printf("%c", s[i]);
print(i + 1, k - 1);
if(s[i] == '(')printf(")");
else printf("]");
print(k + 1, j);
}
}
int main()
{
while(gets(s))
{
int len = strlen(s);
if(len == 0)
{
printf("\n");
continue;
}
memset(dp, 0, sizeof(dp[0][0] * MAX * MAX));
memset(path, 0, sizeof(path[0][0] * MAX * MAX));
for(int i = 0; i < len; ++i)dp[i][i] = 1;
for(int j = 0; j < len; ++j)
{
for(int i = j - 1; i >= 0; --i)
{
//assume s[i] doesn't match
dp[i][j] = dp[i + 1][j] + 1;
path[i][j] = -1;
for(int k = i + 1; k <= j; ++k)
{
if(s[i] == '(' && s[k] == ')' || s[i] == '[' && s[k] == ']')
{
int cost = dp[i + 1][k - 1] + dp[k + 1][j];
if(cost < dp[i][j])
{
dp[i][j] = cost;
path[i][j] = k;//s[k] matches s[i]
}
}
}
}
}
print(0, len - 1);
printf("\n");
}
}

No comments:

Post a Comment