LNACS - VOI10 - Dãy con chung không liền kề dài nhất
Tác giả: happyboy99x
Ngôn ngữ: C++
#include <cstdio>
#define SZ 1005
#define REP(i, n) for( int i = 0, _n = (n); i < _n; ++i )
int a[SZ], b[SZ], f[SZ][SZ];
int n, m;
int main() {
scanf( "%d%d", &m, &n );
REP(i, m) scanf( "%d", a + i );
REP(i, n) scanf( "%d", b + i );
REP(i, m+1) REP(j, n+1)
if ( i == 0 || j == 0 ) f[i][j] = 0;
else if ( i == 1 || j == 1 ) f[i][j] = a[i-1] == b[j-1] ? 1 : f[i-1][j] > f[i][j-1] ? f[i-1][j] : f[i][j-1];
else f[i][j] = a[i-1] == b[j-1] ? f[i-2][j-2] + 1 : f[i-1][j] > f[i][j-1] ? f[i-1][j] : f[i][j-1];
printf( "%d\n", f[m][n] );
return 0;
}