HRBUST 1834【区间dp裸题】

题意：给出一个括号序列括号类型包括'(',')','[',']'求最大的括号匹配数。

套模板即可a。

#include
#include
#include
#define MAX 100+10
#define INF 0x1f1f1f1f
using namespace std;
char str[MAX];
int dp[MAX][MAX];
int max(int a, int b) {return (a > b) ? a : b;
}bool match(char a, char b) {if (a == '(' && b == ')')return true;else if (a == '['&&b == ']')return true;elsereturn false;
}int main(void) {while (~scanf("%s", str + 1)) {int n = strlen(str + 1);memset(dp, 0, sizeof(dp));for (int len = 1; len <= n; len++) {for (int l = 1, r; (r = l + len) <= n; l++) {if (match(str[l], str[r])) {dp[l][r] = max(dp[l + 1][r - 1] + 2, dp[l][r]);}for (int k = l; k < r; k++) {dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r]);}}}printf("%d\n", dp[1][n]);}}

转载于:https://www.cnblogs.com/tennant/p/8976467.html