Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

rejudge成了WA

Posted by phoenixzz at 2007-11-07 21:53:42 on Problem 1141
不知道哪里错了

#include <cstdio>
#include <cstring>

#define MAXN 210
#define min(a,b) a<b?a:b

char str[MAXN];
int res[MAXN][MAXN];
int status[MAXN][MAXN];
int len;

bool match(char c1,char c2)
{
	if((c1=='(' && c2==')') || (c1=='[' && c2==']'))
		return true;
	return false;
}

void get_ans()
{
	int i,j,k;
	int m;
	for(i=1;i<=len;i++)
		res[i][i]=1;
	for(i=2;i<=len;i++)
	{
		for(j=0;j<=len-i;j++)
		{
			if(match(str[1+j],str[i+j]))
				m=0;
			else
				m=2;

			res[1+j][i+j]=res[2+j][i+j]+1;
			status[1+j][i+j]=1+j;


			for(k=j+2;k<j+i;k++)
			{
				if(res[1+j][i+j]>res[1+j][k]+res[k+1][i+j])
				{
					res[1+j][i+j]=res[1+j][k]+res[k+1][i+j];
					status[1+j][i+j]=k;
				}
			}

			if(res[1+j][i+j]>res[j+2][i+j-1]+m)
			{
				res[1+j][i+j]=res[j+2][i+j-1]+m;
				status[1+j][i+j]=0;
			}
		}
	}
	/*for(i=1;i<=len;i++)
	{
		for(j=1;j<=len;j++)
			printf("%3d",res[i][j]);
		printf("\n");
	}
	printf("\n");
	for(i=1;i<=len;i++)
	{
		for(j=1;j<=len;j++)
			printf("%3d",status[i][j]);
		printf("\n");
	}*/
}

void print_ans(int s,int e)
{
	if(s==e)
	{
		switch (str[s])
		{
			case '(':
			case ')':
				printf("()");
				break;
			case '[':
			case ']':
				printf("[]");
				break;
		}
		return;
	}
	if(status[s][e]==0)
	{
		printf("%c",str[s]);
		if(s+1<e)
			print_ans(s+1,e-1);
		printf("%c",str[e]);
		return;
	}
	print_ans(s,status[s][e]);
	print_ans(status[s][e]+1,e);
}

int main()
{
	int i;
	char c;

	scanf("%s",str+1);
	//str[1]='\0';
	len=strlen(str+1);
		get_ans();
		print_ans(1,len);
	printf("\n");
	return 0;
}



Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator