Hướng dẫn giải của VOI 10 Bài 1 - Dãy con chung không liền kề dài nhất
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận