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

void p(int i, int j);

int C[100][100];
int A[100][100];
char b[100];
int l = 0, i, j, k, tmp;

int main(void)
{
	while(gets(b))
	{
		l = strlen(b);
		for(i = l-1; i>=0; --i)
		{
			A[i][i] = 1;
			for(j = i+1; j<l; ++j)
			{
				if(( (b[i]=='(') && (b[j]==')') )||( (b[i]=='[') && (b[j]==']')))
				{
					if((j-1)<(i+1))
						A[i][j] = 0;
					else
						A[i][j] = A[i+1][j-1];
					C[i][j] = -1;
				}
				else
				{
					A[i][j]=pow(2,31)-1;
					for(k = i; k<j; ++k)
					{
						tmp = A[i][k]+A[k+1][j];
						if(tmp<A[i][j])
						{
							A[i][j]=tmp;
							C[i][j]=k;
						}
					}
				}
			}
		}
		p(0,l-1);
		printf("\n");
	}
	return 0;
}

void p(int i, int j)
{
	if(i>j)
		return;
	else if(i==j)
	{
		switch(b[i])
		{
		case '(':;
		case ')':
			printf("()");
			break;
		case '[':;
		case ']':
			printf("[]");
			break;
		}
	}
	else
	{
		if(C[i][j]==-1)
		{
			printf("%c",b[i]);
			p(i+1,j-1);
			printf("%c",b[j]);
		}
		else
		{
			p(i,C[i][j]);
			p(C[i][j]+1,j);
		}
	}
}

• Re:感觉很标准的DP题啊，为啥就是做不对呢？ (12) woaichuiniu 2007-08-07 17:05:39