Brackets

Time Limit:?1000MS	?	Memory Limit:?65536K
Total Submissions:?11633	?	Accepted:?6145

Description

We give the following inductive definition of a “regular brackets” sequence:

• the empty sequence is a regular brackets sequence,
• if?s?is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
• if?a?and?b?are regular brackets sequences, then?ab?is a regular brackets sequence.
• no other sequence is a regular brackets sequence

For instance, all of the following character sequences are regular brackets sequences:

(), [], (()), ()[], ()[()]

while the following character sequences are not:

(, ], )(, ([)], ([(]

Given a brackets sequence of characters?a1a2?…?an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of?s. That is, you wish to find the largest?msuch that for indices?i1,?i2, …,?im?where 1 ≤?i1?<?i2?< … <?im?≤?n,?ai1ai2?…?aim?is a regular brackets sequence.

Given the initial sequence?([([]])], the longest regular brackets subsequence is?[([])].

Input

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters?(,?),?[, and?]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

Sample Input

((())) ()()() ([]]) )[)( ([][][) end

Sample Output

6 6 4 0 6

Source

Stanford Local 2004

?題目大意：給出一個括號序列，求出其中括號最大匹配數量

?第一步：確定狀態(tài)

?f[i][j] 表示ai……aj的串中，有多少個已經匹配的括號

?第二步：確定狀態(tài)轉移方程

?如果ai與aj是匹配的

?f[i][j] = f[i + 1][j - 1] + 2

?否則f[i][j] = max(f[i][j],f[i][k] + f[k + 1][j])

?（相當于是將i到j分成[xxxxx]xxxxx兩部分）

?邊界 f[i][i] = 0

//#include<bits/stdc++.h> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=150; int dp[maxn][maxn];//表示字符串s的第i..j字符需要最少括號數 char a[maxn]; bool cmp(int n,int m) {if((n=='('&&m==')')||(n=='['&&m==']'))return 1;return 0; } int main() {//while(scanf("%s",a)!=EOF){while(scanf("%s",a+1)!=EOF&&a[1]!='e'){//下標從1開始memset(dp,0,sizeof(dp));int n=strlen(a+1);for(int len=2;len<=n;len++){for(int i=1;i<=n;i++){int j=i+len-1;if(j>n) break;if(cmp(a[i],a[j]))//如果ai與aj是匹配的{if(i+1>j-1) dp[i][j]=2;//中間長度為0else dp[i][j]=dp[i+1][j-1]+2;}for(int k=i;k<j;k++)//中斷點{dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);}}}printf("%d\n",dp[1][n]);}return 0; }

?

總結

以上是生活随笔為你收集整理的poj2955 Brackets 最大括号匹配 区间动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。