4107823_ac_188ms_244k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int dp[101][101];
char str[101];

int max(int a, int b)
{
	return a > b ? a : b;
}

int f(int l, int r)
{
	if (dp[l][r] != -1)
		return dp[l][r];
	if (l >= r)
		return dp[l][r] = 0;
	int ans = 0;
	if ((str[l] == '(' && str[r] == ')') || (str[l] == '[' && str[r] == ']'))
		ans = max(ans, 2 + f(l + 1, r - 1));
	for (int k = l; k < r; k++)
		ans = max(ans, f(l, k) + f(k + 1, r));
	return dp[l][r] = ans;
}

int main()
{
	while (scanf("%s", str) == 1)
	{
		if (str[0] == 'e')
			break;
		memset(dp, -1, sizeof(dp));
		printf("%d\n", f(0, strlen(str) - 1));
	}
	return 0;
}