poj-2955-Brackets-區間DP

poj-2955-Brackets-區間DP

?

Brackets

Time Limit:?1000MS	?	Memory Limit:?65536K
Total Submissions:?9014	?	Accepted:?4829

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?a₁a₂?…?a_n, 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?i₁,?i₂, …,?i_m?where 1 ≤?i₁?<?i₂?< … <?i_m?≤?n,?a_i1a_i2?…?a_im?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

?

?

一開始使用code2，找到總的pair數量再*2，以為就解決了。但是wrong answer，不知道本code的方法錯在哪里？

使用了區間DP，方法參考自：?http://www.cnblogs.com/kuangbin/archive/2013/04/29/3051402.html

?

2955

Accepted

472K

47MS

G++

858B

2017-09-16 11:12:08

?

#include <cstdio> 
#include <cstring>const int MAXN = 110; #define max(a, b) (a)>(b)?(a):(b) char ch[MAXN]; 
int dp[MAXN][MAXN]; int Solve(int l, int r){if(dp[l][r] != -1){return dp[l][r]; }if(l>=r){dp[l][r] = 0; return 0; }else if(r == l +1 ){if((ch[l]=='(' && ch[r]==')') ||  (ch[l]=='[' && ch[r]==']') ){dp[l][r] = 2; }else{dp[l][r] = 0; }return dp[l][r]; }dp[l][r] = Solve(l+1, r); for(int k=l+1; k<=r; ++k){if((ch[l]=='(' && ch[k]==')') || (ch[l]=='[' && ch[k]==']')  ){dp[l][r] = max(dp[l][r], 2+Solve(l+1, k-1) + Solve(k+1, r)); }}return dp[l][r]; 
}int main(){freopen("in.txt", "r", stdin); while(scanf("%s", ch) != EOF){getchar(); if(strcmp(ch, "end") == 0){break; }int len = strlen(ch); memset(dp, -1, sizeof(dp)); int ans = Solve(0, len-1); printf("%d\n", ans );}return 0; 
}

　　

?

采用count的方式來計算 subsequence，不知道wrong answer的地方是啥？

?

#include <cstdio>  
#include <cstdlib>  #include <cstring> const int MAXN = 12; int main(){freopen("in.txt", "r", stdin);  int ans, f1,f2, len; char ch[MAXN]; while(scanf("%s", ch) != EOF){getchar(); if(strcmp(ch, "end") == 0){break; } len = strlen(ch); ans = 0;f1 = 0; f2 = 0;  for(int i=0; i<len; ++i){if(ch[i] == '('){++f1; }else if(ch[i] == '['){++f2; }else if(ch[i] == ')'){if(f1 > 0){++ans; --f1; }}else if(ch[i] == ']'){if(f2 > 0){++ans; --f2; }}}printf("%d\n", 2*ans );} return 0; 
} 

　　

?