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

wa了好几次 假设你的dp正确 wa的原因是要么没有注意空行的输入 要么是保存最终答案的字符串数组开得太小

Posted by zengshiyuan at 2014-03-29 09:18:22 on Problem 1141
//我的程序是一边dp一边生成答案 没有用递归去输出答案 那我不太会
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[101][101];
char s[101],ans[101][101][201];
bool check(char c1,char c2)
{
	return((c1=='[' && c2==']')||(c1=='(' && c2==')'));
}
int main()
{
	int i,j,k,l,n;
	gets(s);
    if(strlen(s))
    {
		if(s[strlen(s)-1]==' ') 
		{
			cout<<endl;
			return 0;
		}
		n=strlen(s)-1;
		for(i=0;i<=n;i++)
		{
			for(j=0;j<=n;j++) dp[i][j]=100000;
			
		}
		for(i=0;i<n;i++)
		{
			if(!check(s[i],s[i+1])) 
			{
				dp[i][i+1]=2;
				if(s[i]=='[' || s[i]==']') ans[i][i+1][0]='[',ans[i][i+1][1]=']';
				else ans[i][i+1][0]='(',ans[i][i+1][1]=')';
				if(s[i+1]=='[' || s[i+1]==']') ans[i][i+1][2]='[',ans[i][i+1][3]=']';
				else ans[i][i+1][2]='(',ans[i][i+1][3]=')';
				ans[i][i+1][4]='\0';
			}
			else dp[i][i+1]=0,ans[i][i+1][0]=s[i],ans[i][i+1][1]=s[i+1],ans[i][i+1][2]='\0';
			dp[i][i]=1;
			if(s[i]=='[' || s[i]==']') ans[i][i][0]='[',ans[i][i][1]=']';
				else ans[i][i][0]='(',ans[i][i][1]=')';
			ans[i][i][2]='\0';
		};
		dp[n][n]=1;
		if(s[n]=='[' || s[n]==']') ans[n][n][0]='[',ans[n][n][1]=']';
			else ans[n][n][0]='(',ans[n][n][1]=')';
		ans[i][i][2]='\0';
		for(l=3;l<=n+1;l++)
			for(i=0;i<=n-l+1;i++)
			{
				j=i+l-1;
				ans[i][j][0]='\0';
				if(check(s[i],s[j]))
				{
					dp[i][j]=dp[i+1][j-1];
					ans[i][j][0]=s[i];
					ans[i][j][1]='\0';
					strcat(ans[i][j],ans[i+1][j-1]);
					k=strlen(ans[i+1][j-1]);
					ans[i][j][k+1]=s[j];
					ans[i][j][k+2]='\0';
				}
				for(k=i;k<j;k++)
					if(dp[i][j]>dp[i][k]+dp[k+1][j])
					{
						dp[i][j]=dp[i][k]+dp[k+1][j];
						strcpy(ans[i][j],ans[i][k]);
						strcat(ans[i][j],ans[k+1][j]);
					}
			}
		cout<<ans[0][n]<<endl;
	}
    else printf("\n");
}

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