最长公共子序列LCS

 1 #include<iostream>
 2 #include<cstdio>
 3 #define maxn 10010
 4 using namespace std;
 5 template<typename T>
 6 inline void read(T &x){
 7     x=0; bool flag=0; char c=getchar();
 8     for(;!isdigit(c);c=getchar()) if(c==‘-‘) flag=1;
 9     for(;isdigit(c);c=getchar()) x=x*10+(c^48);
10     if(flag) x=-x;
11 }
12 
13 int n;
14 int a[maxn],b[maxn],f[maxn][maxn];
15 
16 int main(){
17     read(n);
18     for(int i=1;i<=n;i++) read(a[i]);
19     for(int i=1;i<=n;i++) read(b[i]);
20     for(int i=1;i<=n;i++){
21         for(int j=1;j<=n;j++){
22             f[i][j]=max(f[i-1][j],f[i][j-1]);
23             if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
24         }
25     }
26     printf("%d\n",f[n][n]);
27     return 0;
28 }