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

我晕,2次MLE,2次TLE,终于水走

Posted by dynamic_study at 2009-07-01 16:23:16 on Problem 1159
//dynamic_study 1159 Accepted 49484K 1641MS C++ 961B 
//悲哀啊,给我指点指点啊,我新手,不知道怎么弄
#include<iostream>
using namespace std;
short **dp,len;
int LCS(char *s1,char *s2)
{
	int i,j;
	for(i=0;i<=len;i++)
	{
		dp[0][i]=0;
		dp[i][0]=0;
	}
	for(i=1;i<=len;i++)
	{
		for(j=1;j<=len;j++)
		{
			if(s1[i-1]==s2[j-1])
				dp[i][j]=dp[i-1][j-1]+1;
			else
			{
				if(dp[i][j-1]>dp[i-1][j])
					dp[i][j]=dp[i][j-1];
				else
					dp[i][j]=dp[i-1][j];

			}
		}
	}
//	cout<<dp[len][len]<<endl;
	return dp[len][len];
	


}
int main()
{
	char *str,*str1;
	int ans,i;
	cin>>len;
	str=new char [len+3];
	str1=new char [len+3];
	 dp=new short *[len+3];
	for(i=0;i<len+3;i++)
	   dp[i]=new short [len+3];
	cin>>str;
	for(i=0;i<len;i++)
	{
		str1[i]=str[len-i-1];
	}
	str1[len]='\0';

	//cout<<str<<" "<<str1<<endl;
	ans=LCS(str,str1);
	//cout<<ans<<endl;
	cout<<len-ans<<endl;
	//for(i=0;i<len+3;i++)
	//	delete [] dp[i];
	//delete []dp;
	//dp=0;
	//delete [] str;
	//delete [] str1;
	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