#include<iostream>
#include<string.h>
#include<stdio.h>
#define inf 9999
using namespace std;
char str[110];
int dp[110][110];
int v[110][110];
int dps(int i,int j)
{
	int k;
	if(dp[i][j]!=inf)
		return dp[i][j];//已经找到了i到j形成合法串的最短长度
	if(i==j)
	{
		dp[i][j]=2;//相等则添加另一半
		v[i][i]=i;//i到i只经过了自己方便后面的输出
	}
	else if(i==j+1)//考虑遇到()或是[]情况后...
		return 0;
	else if(str[i]=='('&&str[j]==')'||str[i]=='['&&str[j]==']')
	{
		v[i][j]=-1;
		dp[i][j]=dps(i+1,j-1)+2;
		return dp[i][j];
	}
	else for(k=i;k<j;k++)
	{
		dp[i][k]=dps(i,k);
		dp[k+1][j]=dps(k+1,j);
		if(dp[i][j]>dp[i][k]+dp[k+1][j])
		{
			dp[i][j]=dp[i][k]+dp[k+1][j];
			v[i][j]=k;//分割成两块(i,k)和（k+1,j)
		}
	}
	return dp[i][j];//返回已经更新好的值
}
void print(int i,int j)
{
	if(i==j+1)
		return ;
	else if(i==j)
	{
		if(str[i]=='('||str[i]==')')printf("()");
		if(str[i]=='['||str[i]==']')printf("[]");
	}
	else if(v[i][j]!=-1)
	{
		print(i,v[i][j]);
		print(v[i][j]+1,j);
	}
	else
	{
		printf("%c",str[i]);
		print(i+1,j-1);
		printf("%c",str[j]);
	}
	return ;
}
int main()
{
	while(gets(str))
	{
		int i,j;
		int n=strlen(str);
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				dp[i][j]=inf;
				v[i][j]=-3;
			}

		}
		dps(0,n-1);
		print(0,n-1);
		printf("\n");
	}

	return 0;
}

• Re:有没有大神看看错在哪里啊？纠结啊！ (15) dyx404514 2012-07-11 15:32:02