题目链接：http://poj.org/problem?id=2955
题意：给出一个由小括号和中括号组成的字符串，求最长匹配子序列的长度。
思路：使用区间 DP。dp[i][j] 表示从 i 到 j 的最长匹配子序列长度。显然，当 i 和 j 位置的括号匹配时，dp[i][j] = dp[i+1][j-1] + 2。接下来，我们只需要枚举不属于两端的中间点 k，更新 dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j]) 即可。
题解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[105][105];
char s[105];
int main(){
while(scanf("%s", s), strcmp(s, "end")){
memset(dp, 0, sizeof(dp));
int len = strlen(s);
for(int l = 1; l < len; l++){
for(int i = 0; i < len - l; i++){
int j = i + l;
if((s[i]=='(' && s[j]==')') || (s[i]=='[' && s[j]==']')){
dp[i][j] = dp[i+1][j-1] + 2;
}
for(int k = i + 1; k < j; k++){
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
printf("%d\n", dp[0][len-1]);
}
return 0;
}
|
