3239701_ac_32ms_268k.cpp

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

#include <stdio.h>
#include <string.h>
#define L 105
#define INF 500

char str[L];
int dp[L][L], caled[L][L];
int len;

int min(int x, int y)
{
	return x < y ? x : y;
}

int DP(int l, int r)
{
	int i, ans;

	if (l > r)
		return 0;
	if (caled[l][r])
		return dp[l][r];
caled[l][r] = 1;
	if (l == r)
	{
		dp[l][r] = 1;
		caled[l][r] = 1;
		return 1;
	}

	ans = INF;
	if ( (str[l] == '(' && str[r] == ')') || (str[l] == '[' && str[r] == ']') )
		ans = min(ans, DP(l+1, r-1));
	for (i = l; i < r; i++)
		ans = min(ans, DP(l, i) + DP(i+1, r));
	dp[l][r] = ans;
	
	return ans;
}

void print(int l, int r)
{
	int i;

	if (l > r)
		return ;

	if (l == r)
	{
		if (str[l] == '(' || str[l] == ')')
			printf("()");
		else
			printf("[]");
		return ;
	}

	if (dp[l][r] == dp[l+1][r-1] && ( (str[l] == '(' && str[r] == ')') || (str[l] == '[' && str[r] == ']') ))
	{
		printf("%c", str[l]);
		print(l+1, r-1);
		printf("%c", str[r]);
		return ;
	}

	for (i = l; i < r; i++)
	{
		if (dp[l][r] == dp[l][i] + dp[i+1][r])
		{
			print(l, i);
			print(i+1, r);
			return ;
		}
	}
}

int main()
{
	scanf("%s", str);
	{
		memset(dp, 0, sizeof(dp));
		memset(caled, 0, sizeof(caled));
		len = strlen(str);
		DP(0, len-1);
		print(0, len-1);
		printf("\n");
	}

	return 0;
}