首页 > 代码库 > POJ 2955：Brackets（区间DP）
POJ 2955：Brackets（区间DP）
http://poj.org/problem?id=2955
题意：给出一串字符，求括号匹配的数最多是多少。
思路：区间DP。
对于每个枚举的区间边界，如果两边可以配对成括号，那么dp[i][j] = dp[i+1][j-1] + 2，表示由上一个状态加上当前的贡献。
然后和普通的区间合并一样去更新。
1 #include <cstring> 2 #include <cstdio> 3 #include <iostream> 4 #include <string> 5 using namespace std; 6 #define N 105 7 int dp[105][105]; 8 string s; 9 10 int main() {11 while(cin >> s) {12 if(s == "end") break;13 int n = s.length();14 memset(dp, 0, sizeof(dp));15 for(int len = 1; len < n; len++) {16 for(int i = 0; i + len < n; i++) {17 int j = i + len;18 if(s[i] == ‘(‘ && s[j] == ‘)‘ || s[i] == ‘[‘ && s[j] == ‘]‘) dp[i][j] = 2 + dp[i+1][j-1];19 for(int k = i; k < j; k++)20 if(dp[i][j] < dp[i][k] + dp[k+1][j]) dp[i][j] = dp[i][k] + dp[k+1][j];21 }22 }23 printf("%d\n", dp[0][n-1]);24 }25 return 0;26 }
POJ 2955：Brackets（区间DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。