LNACS - VOI10 - Dãy con chung không liền kề dài nhất
Tác giả: RR
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(long i=a; i<=b; i++)
#define MAXN 1011
using namespace std;
long m,n,a[MAXN],b[MAXN],f[MAXN][MAXN];
int main() {
scanf("%ld %ld",&m,&n);
FOR(i,2,m+1) scanf("%ld",&a[i]);
FOR(j,2,n+1) scanf("%ld",&b[j]);
FOR(i,2,m+1)
FOR(j,2,n+1)
if (a[i]==b[j]) f[i][j]=f[i-2][j-2]+1;
else f[i][j]=max(f[i-1][j],f[i][j-1]);
printf("%ld\n",f[m+1][n+1]);
return 0;
}