首页 > 代码库 > POJ 2955 Brackets

POJ 2955 Brackets

2024-07-29 03:23:11   223人阅读

传送门@百度

Brackets
Time Limit: 1000MS Memory Limit: 65536K
   

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 m such 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

66406

Source

Stanford Local 2004

继续刷水，和上一题差不多,dp[i][j]=max(dp[i+1][j-1]+1//i,j匹配,dp[i][k]+dp[k+1][j]);

 1 #include<set> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<iostream> 6 #include<algorithm> 7 using namespace std; 8 const int N = 110; 9 #define For(i,n) for(int i=1;i<=n;i++)10 #define Rep(i,l,r) for(int i=l;i<=r;i++)11 #define Down(i,r,l) for(int i=r;i>=l;i--)12 13 char s[N];14 int dp[N][N],n;15 //dp[i][j]=max{dp[i+1][j-1]+1,dp[i][k]+dp[k+1][j]}16 17 bool match(char A,char B){18     if(A==‘(‘) return (B==‘)‘);19     if(A==‘[‘) return (B==‘]‘);20     return false;21 }22 23 void DP(){24     memset(dp,0,sizeof(dp));25     n=strlen(s+1);26     Down(i,n-1,1)27       Rep(j,i+1,n){28           if(match(s[i],s[j])) dp[i][j]=dp[i+1][j-1]+1;29           Rep(k,i,j-1)30             dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);31       }32     cout<<dp[1][n]*2<<endl;33 }34 35 int main(){36     while(scanf("%s",s+1),strcmp(s+1,"end")){37         DP();38     }39     return 0;40 }
Codes

 

POJ 2955 Brackets


联系
我们