国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > 综合技术 > 【POJ 2955】Brackets(区间DP)

【POJ 2955】Brackets(区间DP)

来源:程序员人生   发布时间:2016-09-30 10:51:46 阅读次数:2313次

【POJ 2955】Brackets(区间DP)

入门级区间DP

问最长的匹配括号长度。只包括()和[]
要求匹配括号不可交叉,即([)]这类不计入

由于不计交叉情况,转移就很直白。

枚举区间长度l,转移为

if( (str[i] == '(' && str[i+l-1] == ')') || (str[i] == '[' && str[i+l-1] == ']') ) dp[i][i+l-1] = max(dp[i][i+l-1],dp[i+1][i+l-2]+2); //合并相邻区间最长括号匹配数 for(int j = i; j < i+l; ++j) dp[i][i+l-1] = max(dp[i][i+l-1],dp[i][j]+dp[j+1][i+l-1]);

代码以下:

#include <iostream> #include <cmath> #include <vector> #include <cstdlib> #include <cstdio> #include <climits> #include <ctime> #include <cstring> #include <queue> #include <stack> #include <list> #include <algorithm> #include <map> #include <set> #define LL long long #define Pr pair<int,int> #define fread(ch) freopen(ch,"r",stdin) #define fwrite(ch) freopen(ch,"w",stdout) using namespace std; const int INF = 0x3f3f3f3f; const int msz = 10000; const int mod = 1e9+7; const double eps = 1e⑻; char str[233]; int dp[233][233]; bool cal(int i,int j) { return (str[i] == '(' && str[j] == ')') || (str[i] == '[' && str[j] == ']'); } int main() { //fread(""); //fwrite(""); while(~scanf("%s",str) && str[0] != 'e') { int len = strlen(str); memset(dp,0,sizeof(dp)); for(int l = 2; l <= len; l++) { for(int i = 0; i+l <= len; ++i) { if(cal(i,i+l-1)) dp[i][i+l-1] = max(dp[i][i+l-1],dp[i+1][i+l-2]+2); for(int j = i; j < i+l; ++j) dp[i][i+l-1] = max(dp[i][i+l-1],dp[i][j]+dp[j+1][i+l-1]); } } printf("%d\n",dp[0][len-1]); } return 0; }
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生