程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA1626 / ZOJ1463 Brackets sequence 區間DP

UVA1626 / ZOJ1463 Brackets sequence 區間DP

編輯：C++入門知識

UVA1626 / ZOJ1463 Brackets sequence 區間DP

簡單區間DP (有空串... ...)

Brackets sequence Time Limit: 4500MS Memory Limit: Unknown 64bit IO Format: %lld & %llu

Submit Status

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 a₁a₂...a_n is called a subsequence of the string b₁b₂...b_m, if there exist such indices 1 ≤ i₁ < i₂ < ... < i_n ≤ m, that a_j=b_{i_j} for all 1 ≤ j ≤ n.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

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

1

([(]

Sample Output

()[()]

Source

Root :: AOAPC II: Beginning Algorithm Contests (Second Edition) (Rujia Liu) :: Chapter 9. Dynamic Programming :: Examples

Submit Status

/* ***********************************************
Author        :CKboss
Created Time  :2015年02月11日 星期三 16時15分08秒
File Name     :ZOJ1463.cpp
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int maxn=300;
const int INF=0x3f3f3f3f;

char str[maxn];
int n;
int dp[maxn][maxn];

bool match(int a,int b)
{
	if((str[a]=='('&&str[b]==')')||(str[a]=='['&&str[b]==']'))
		return true;
	return false;
}

void PRINT(int l,int r)
{
	if(l==r)
	{
		if(str[l]=='('||str[l]==')')
		{
			putchar('('); putchar(')');
		}
		if(str[l]=='['||str[l]==']')
		{
			putchar('['); putchar(']');
		}
		return ;
	}
	else if(l>r) return ;
	int pos=-1;
	int temp=INF;
	if(match(l,r)) temp=dp[l+1][r-1];
	for(int i=l;i+1<=r;i++)
		if(dp[l][i]+dp[i+1][r]j) dp[i][j]=0;
		for(int len=2;len<=n;len++)
		{
			for(int i=0;i+len-1