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.

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

Please read the guidelines before commenting.


There are no comments at the moment.