| ||||||||||
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