2537922_ac_15ms_144k.cpp

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

#include <stdio.h>
#include <string.h>
#define INF 1000000

int min(int a,int b)
{ 
	return a<b?a:b;
}
char str[101];
int DP[101][101];
int caled[101][101];

int dp(int i,int j)
{
	int k, ans;

	if(caled[i][j])
		return DP[i][j];
	if(i>j)
		return 0;
	if(i==j)
	{
		caled[i][j] = 1;
		DP[i][j] = 1;
		return 1;
	}
	ans = INF;
	if(str[i]=='('&&str[j]==')')
		ans = min(ans,dp(i+1,j-1));
	if(str[i]=='['&&str[j]==']')
		ans = min(ans,dp(i+1,j-1));
	for(k = i; k < j; k++)
		ans = min(ans,dp(i,k)+dp(k+1,j));
	DP[i][j] = ans;
	caled[i][j] = 1;
	return ans;
}

void solve(int i,int j)
{
	int k;

	if(i==j)
	{
		if(str[i]=='('||str[i]==')')
			printf("()");
		else
			printf("[]");
		return ;
	}
	if(DP[i+1][j-1]==DP[i][j]&&((str[i]=='['&&str[j]==']')||(str[i]=='('&&str[j]==')')))
	{
		printf("%c",str[i]);
		solve(i+1,j-1);
		printf("%c",str[j]);
		return ;
	}
	for(k = i; k < j; k++)
	{
		if(DP[i][j]==DP[i][k]+DP[k+1][j])
		{
			solve(i,k);
			solve(k+1,j);
			return ;
		}
	}
}

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