首页 > 代码库 > poj 1114

poj 1114

2024-08-02 09:34:41   221人阅读

Brackets Sequence
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 25989 Accepted: 7330 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.

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[i][j]表示 i 到 j 最多的匹配个数转移方程：dp[i][j] = max（dp[i][j], dp[i][k] + dp[k+1][j]);#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;const int N = 105;char str[N];int dp[N][N];bool judge(char a, char b){    if(a == ‘(‘ && b == ‘)‘) return true;    if(a == ‘[‘ && b == ‘]‘) return true;    return false;}int main(){    while(gets(str) != NULL)    {        if(!strcmp(str, "end")) break;        int len = strlen(str);        for(int i = 0; i < len; i++)        {            dp[i][i] = 0;            if(judge(str[i], str[i+1]))                dp[i][i+1] = 2;            else                dp[i][i+1] = 0;        }        for(int k = 2; k < len; k++) //枚举子串的长度        {            for(int i = 0; i + k < len; i++)            {                int r = i + k;                dp[i][r] = 0;                if(judge(str[i], str[r]))                    dp[i][r] = dp[i+1][r-1] + 2;                for(int j = i; j < r; j++)                    dp[i][r] = max(dp[i][r], dp[i][j] + dp[j+1][r]);            }        }        printf("%d\n",dp[0][len-1]);    }    return 0;}

　　

poj 1114


联系
我们