Editorial for VOI 10 Bài 1 - Dãy con chung không liền kề dài nhất
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
var a,b:array[1..1000] of longint; i,j,m,n:longint; f:array[-1..1000,-1..1000] of integer; begin read(m,n); for i:=1 to m do read(a[i]); for j:=1 to n do read(b[j]); for i:=-1 to 0 do begin for j:=0 to m do f[i,j]:=0; for j:=0 to n do f[j,i]:=0; end; for i:=1 to m do for j:=1 to n do begin if f[i-1,j]>f[i,j-1] then f[i,j]:=f[i-1,j] else f[i,j]:=f[i,j-1]; if (a[i]=b[j]) and (f[i,j]<f[i-2,j-2]+1) then f[i,j]:=f[i-2,j-2]+1; end; writeln(f[m,n]); end.
Code mẫu của happyboy99x
#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; }
Code mẫu của ladpro98
//cho 2 xau s1,s2 co length <=1000. Tim xau con chung dai nhat. program xaucondainhat; uses math; const maxLength = 1000; var t1,t2:array[1..maxLength] of longint; len: array[-1..maxLength,-1..maxLength] of longint; i,j,res,m,n:longint; procedure input; begin readln(m,n); for i:=1 to m do readln(t1[i]); for j:=1 to n do readln(t2[j]); end; procedure process; var i,j:word; begin for i:=1 to m do for j:=1 to n do if t1[i]=t2[j] then begin len[i,j]:=len[i-2,j-2]+1; end else len[i,j]:=max(len[i-1,j],len[i,j-1]); end; begin input; for i:=1 to m do begin len[i,0]:=0;len[i,-1]:=0;end; for j:=1 to n do begin len[0,j]:=0;len[-1,j]:=0;end; process; res:=len[m,n]; write(res); end.
Code mẫu của RR
#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; }
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> int max(int a,int b) { if(a<b) return b; return a; } main() { int a[1001],b[1001],f[1001][1001],m,n; scanf("%d %d",&m,&n); for(int i=1;i<=m;i++) { scanf("%d",&a[i]); f[i][0]=0; } for(int j=1;j<=n;j++) { scanf("%d",&b[j]); f[0][j]=0; } for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { 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("%d",f[m][n]); // getch(); }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <ctime> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <iostream> #include <map> #include <set> #include <sstream> #include <stack> #include <queue> #include <vector> #include <utility> using namespace std; int a[1010],b[1010],f[1010][1010]; int main() { int n,m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= m; i++) scanf("%d", &b[i]); memset(f,0,sizeof(f)); for (int i = 1; i <= n; i++) f[i][1] = (a[i] == b[1]) ? 1 : f[i - 1][1]; for (int i = 1; i <= m; i++) f[1][i] = (a[1] == b[i]) ? 1 : f[1][i - 1]; for (int i = 2; i <= n; i++) for (int j = 2; j <= m; j++) { f[i][j] = max(f[i - 1][j],f[i][j - 1]); if (a[i] == b[j]) f[i][j] = max(f[i][j],f[i - 2][j - 2] + 1); }; printf("%d\n", f[n][m]); };
Code mẫu của skyvn97
program LNACS; const MAXN=1111; var m,n:integer; a,b:array [-1..MAXN] of integer; f,g:array [-1..MAXN,-1..MAXN] of integer; function max(x,y,z:integer):integer; begin if (x>=y) and (x>=z) then exit(x); if (y>=x) and (y>=z) then exit(y); if (z>=x) and (z>=y) then exit(z); end; procedure init; var i:integer; begin read(m,n); for i:=1 to m do read(a[i]); for i:=1 to n do read(b[i]); end; procedure optimize; var i,j,res:integer; begin res:=0; for i:=1 to m do for j:=1 to n do begin if a[i]=b[j] then f[i,j]:=g[i-2,j-2]+1; if f[i,j]>res then res:=f[i,j]; g[i,j]:=max(g[i-1,j],g[i,j-1],f[i,j]); end; write(res); end; begin init; optimize; end.
Code mẫu của khuc_tuan
#include <iostream> using namespace std; int m, n, a[1010], b[1010]; int F[1010][1010]; int main() { cin >> m >> n; for(int i=2;i<=m+1;++i) cin >> a[i]; for(int i=2;i<=n+1;++i) cin >> b[i]; for(int i=2;i<=m+1;++i) for(int j=2;j<=n+1;++j) { F[i][j] = max( F[i-1][j], F[i][j-1]); if(a[i] == b[j]) F[i][j] = max( F[i][j], F[i-2][j-2] + 1); } cout << F[m+1][n+1] << endl; return 0; }
Comments