| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
我晕,2次MLE,2次TLE,终于水走//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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator