POJ 2955 Brackets

皮康龙发布

题目链接: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]) 即可。

题解:

#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;
}
分类: 未分类

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注