首页 > 其他 > 详细

POJ 2955:Brackets(区间DP)

时间:2017-02-27 01:00:23      阅读:158      评论:0      收藏:0      [点我收藏+]

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)

原文:http://www.cnblogs.com/fightfordream/p/6460906.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!