POJ 2955 Brackets——区间dp

POJ 2955 Brackets——区间dp

做过很多括号序列的题以后，感觉这类题都是老套路了

dp[i][j]表示闭区间【i，j】内最长的匹配好的括号子序列，并全部初始化为0

#include #include #include #include using namespace std;const int maxn = 110;char str[maxn];int dp[maxn][maxn], n;bool match(char a, char b) { if ( (a == '(' && b == ')') || (a == '[' && b == ']') ) return true; else return false;}int main(){ while (gets(str) != NULL) { if (str[0] == 'e') break; memset(dp, 0, sizeof(dp)); n = strlen(str) - 1; for (int i = n - 1; i >= 0; i--) { for (int j = i + 1; j <= n; j++) { if (match(str[i], str[j])) dp[i][j] = dp[i + 1][j - 1] + 2; for (int k = i; k < j; k++) { dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]); } } } printf("%d\n", dp[0][n]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。