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

没有记忆化。

Posted by luishen at 2011-07-22 17:06:44 on Problem 1458
In Reply To:TLE，请教出错之处 Posted by:lyhypacm at 2009-12-19 21:03:04
```#include <iostream>
#include <cstring>
#include <fstream>
//#define cin fin
using namespace std;
//ifstream fin("data.txt");
int Max(int a,int b){
return a > b ?  a : b;
}

char a[202];
char b[202];
short f[202][202];

int LCS(int len_a,int len_b){
if (f[len_a][len_b]!=-1) return f[len_a][len_b];

if (len_a==0 || len_b==0) {
f[len_a][len_b]=0;
return 0;
}

if (a[len_a-1]==b[len_b-1])
f[len_a][len_b] = LCS(len_a-1,len_b-1)+1;
else
f[len_a][len_b] = Max( LCS(len_a-1,len_b),LCS(len_a,len_b-1));

return f[len_a][len_b];

}

void Init(){
int i;
int j;
for (i=0; i<=201; i++)
for (j=0; j<=201; j++)
f[i][j]=-1;
}
int main(){

while (cin>>a>>b){
Init();
cout<<LCS(strlen(a),strlen(b))<<endl;
}
return 0;
}```

Followed by: