Editorial for VOI 08 Bài 2 - Lò cò

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,d:array[1..1000] of longint;
    n:integer;

procedure rf;
var i:integer;
begin
     readln(n);
     for i:=1 to n do
     begin
          read(a[i]);
          d[i]:=1;
     end;
end;

procedure sort(l,r:integer);
var i,j:integer; x,y:longint;
begin
     i:=l; j:=r; x:=a[(i+j) div 2];
     repeat
           while a[i]<x do i:=i+1;
           while x<a[j] do j:=j-1;
           if i<=j then
           begin
                y:=a[i]; a[i]:=a[j]; a[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

function bs(i,j:integer):integer;
var l,r,m:integer; k:longint;
begin
     k:=a[i]-a[j];
     l:=1; r:=n;
     repeat
           m:=(l+r) div 2;
           if a[m]=k then 
       begin
        if m=j then l:=m+1
        else break;
       end
           else
           begin
                if a[m]<k then l:=m+1
                else r:=m-1;
           end;
     until l>r;
     if a[m]=k then
     begin
          if d[j]>d[m] then bs:=d[j]
          else bs:=d[m];
     end
     else bs:=0;
end;

procedure pr;
var i,j,max:integer;
begin
     sort(1,n);
     for i:=3 to n do
     begin
          max:=0;
          for j:=1 to i-1 do
          begin
               if (bs(i,j)>max) then
                  max:=bs(i,j);
          end;
          d[i]:=d[i]+max;
     end;
end;

procedure wf;
var i,max:integer;
begin
     max:=0;
     for i:=1 to n do
         if d[i]>max then max:=d[i];
     write(max);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 1005

int a[N], f[N], n;

int main() {
    //freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
    scanf( "%d", &n ); rep(i, n) scanf( "%d", a+i );
    sort(a, a+n); fill(f, f+n, 1);
    fo(i, 1, n-1) rep(j, i) {
        int v = a[i] - a[j];
        if(f[j]+1>f[i] && (binary_search(a, a+j, v) || binary_search(a+j+1, a+n, v))) f[i] = f[j]+1;
    }
    //rep(i, n) printf( "%d ", f[i] ); putchar(10);
    printf( "%d\n", *max_element(f, f+n) );
    return 0;
}

Code mẫu của ladpro98

program nkjump;
uses    math;
const   fi='';
        maxN=1111;
var     a,f:array[1..maxN] of longint;
        x:array[1..maxN,1..maxN] of boolean;
        n:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        read(inp,a[i]);
        close(inp);
end;

procedure swap(i,j:longint);
var     t:longint;
begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
end;

procedure sort(l,r:longint);
var     p,i,j:longint;
begin
        if l>=r then exit;
        p:=a[random(r-l+1)+l];
        i:=l;j:=r;
        repeat
                while a[i]<p do inc(i);
                while a[j]>p do dec(J);
                if i<=j then
                begin
                        if i<j then swap(i,j);
                        inc(i);
                        dec(j);
                end;
        until i>j;
        sort(l,j);sort(i,r);
end;

function find(l,key:longint):longint;
var     r,m:longint;
begin
        r:=n;
        while l<=r do
        begin
                m:=(l+r) shr 1;
                if a[m]=key then exit(m);
                if a[m]<key then l:=m+1
                else r:=m-1;
        end;
        exit(0);
end;

procedure init;
var     i,j,pos:longint;
begin
        for i:=1 to n-2 do
        for j:=i+1 to n-1 do
        begin
                pos:=find(j+1,a[i]+a[j]);
                if pos<>0 then
                begin
                        x[i,pos]:=true;
                        x[j,pos]:=true;
                end;
        end;
end;

procedure dp;
var     i,j:longint;
begin

        for i:=1 to n do f[i]:=1;
        for i:=2 to n do
        for j:=i-1 downto 1 do
        if x[j,i] then
        f[i]:=max(f[i],f[j]+1);
end;

procedure output;
var     i,res:longint;
begin
        res:=0;
        for i:=1 to n do
        res:=max(res,f[i]);
        write(res);
end;

begin
        input;
        sort(1,n);
        init;
        dp;
        output;
end.

Code mẫu của RR

uses math;
const
  hashkey=1000003;

type
  list=^node;
  node=record
        u:longint;
        next:list;
  end;

procedure add(u:longint; var a:list);
    var
      p:list;
    begin
      new(p); p^.u:=u;
      p^.next:=a; a:=p;
    end;

var
  h:array[0..hashkey] of list;
  i,j,n:longint;
  a,f:array[0..1011] of longint;

procedure insert(u:longint);
    var
      p:list;
    begin
      p:=h[u mod hashkey];
      while p<>nil do
        begin
          if p^.u=u then exit;
          p:=p^.next;
        end;
      add(u,h[u mod hashkey]);
    end;

function find(u:longint):boolean;
    var
      p:list;
    begin
      p:=h[u mod hashkey];
      while p<>nil do
        begin
          if p^.u=u then exit(true);
          p:=p^.next;
        end;
      exit(false);
    end;

procedure swap(var a,b:longint);
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure sort(l,r:longint);
    var
      i,j,mid:longint;
    begin
      i:=l; j:=r; mid:=a[l+random(r-l+1)];
      repeat
        while a[i]<mid do inc(i);
        while a[j]>mid do dec(j);
        if i<=j then
          begin
            swap(a[i],a[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
    end;

begin
  read(n);
  for i:=1 to n do
    begin
      read(a[i]);
      insert(a[i]);
    end;
  sort(1,n);
  a[0]:=-1000111000;
  a[n+1]:=-a[0];

  for i:=1 to n do
    begin
      f[i]:=1;
      for j:=1 to i-1 do
        if a[i]-a[j]=a[j] then
          begin
            if (a[j-1]<>a[j]) and (a[j]<>a[j+1]) then begin end
            else f[i]:=max(f[i],f[j]+1);
          end
        else if find(a[i]-a[j]) then f[i]:=max(f[i],f[j]+1);
    end;

  j:=0;
  for i:=1 to n do
    j:=max(j,f[i]);
  writeln(j);
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
void Quicksort(long A[],long x,long y)
{               
  long t=A[(x+y)/2];
  long i=x; long j=y;
  while(i<=j)
    {
    while(A[i]<t) i++;
    while(A[j]>t) j--;
    if(i<=j)
      {
      if(A[i]!=A[j])
        {      
        long tg=A[i];
        A[i]=A[j];
        A[j]=tg;
        }
      i++;
      j--;
      }
    }
  if(j>x)  
  Quicksort(A,x,j);
  if(i<y)
  Quicksort(A,i,y);
}
main()
{
long n,a[1001],F[1001],Max=1;
scanf("%ld",&n);
for(long i=1;i<=n;i++)
scanf("%ld",&a[i]);
Quicksort(a,1,n);
//for(long i=1;i<=n;i++)
//printf("%ld ",&a[i]);
F[1]=1;F[2]=1;
for(long i=3;i<=n;i++)
  {
  F[i]=1;       
  long u=1;long v=i-1;
  while(u<v)
    {
    if(a[u]+a[v]>a[i])
      v--;
    else if(a[u]+a[v]<a[i])
      u++;
    else
      {
      if(F[i]<F[u]+1)
        F[i]=F[u]+1;
      if(F[i]<F[v]+1)
        F[i]=F[v]+1;
      u++;
      v--;
      }
    }
  if(Max<F[i])
    Max=F[i];
  }
printf("%ld",Max);
//getch();
}

Code mẫu của ll931110

Program NKJUMP;
        Const
                input  = '';
                output = '';
        Var
                a,F: array[1..1000] of longint;
                  c: array[1..1000,1..1000] of boolean;
                  n: longint;

Procedure init;
          Var
                fi: text;
                 i: longint;
          Begin
                Assign(fi, input);
                        Reset(fi);

                Readln(fi, n);
                For i:= 1 to n do read(fi, a[i]);

                Close(fi);
          End;

Procedure BubbleSort;
          Var
                i,j,t: longint;
          Begin
                For i:= 1 to n - 1 do
                    For j:= i + 1 to n do
                        if a[i] > a[j] then
                                Begin
                                        t:= a[i];
                                        a[i]:= a[j];
                                        a[j]:= t;
                                End;
          End;

Procedure BuildGraph;
          Var
                i,j,k,last: longint;
          Begin
                Fillchar(c, sizeof(c), false);

                For i:= 1 to n - 2 do
                    Begin
                        last:= i + 2;
                        For j:= i + 1 to n - 1 do
                            For k:= last to n do
                                Begin
                                        If a[i] + a[j] = a[k] then
                                                Begin
                                                        c[i,k]:= true;
                                                        c[j,k]:= true;
                                                End
                                        else if a[i] + a[j] < a[k] then break;
                                        last:= k;
                                End;
                    End;
          End;

Procedure Topo;
          Var
                i,j: longint;
          Begin
                For i:= 1 to n do
                    Begin
                        F[i]:= 1;
                        For j:= 1 to i - 1 do if c[j,i]
                                and (F[j] + 1 > F[i]) then F[i]:= F[j] + 1;
                    End;

          End;

Procedure solve;
          Var
                    fo: text;
                 i,res: longint;
          Begin
                Assign(fo, output);
                        Rewrite(fo);

                res:= F[1];
                For i:= 2 to n do if res < F[i] then res:= F[i];

                        Writeln(fo, res);
                Close(fo);
          End;

Begin
        init;
        BubbleSort;
        BuildGraph;
        Topo;
        solve;
ENd.

Code mẫu của khuc_tuan

#include <cstdio>
#include <algorithm>
using namespace std;
int n, aa[1010], na, a[1010], f[1010];
int main() {
    int i, j, t, r=0;
    scanf("%d",&na);
    for(i=0;i<na;++i) scanf("%d",aa+i);
    sort(aa,aa+na);
    for(i=0;i<na;++i) if(n<2 || aa[i]!=a[n-1] || aa[i]!=a[n-2]) a[n++] = aa[i];
    for(i=0;i<n;++i) {
        if(f[i]==0) f[i]=1;
        t = i+1;
        for(j=0;j<i;++j)
            for(;t<n && a[t]<=a[i]+a[j];++t) if(a[t]==a[i]+a[j]) f[t]>?= (f[i]>?f[j])+1;
    }
    printf("%d\n",*max_element(f,f+n));
    return 0;
}

Comments

Please read the guidelines before commenting.

There are no comments at the moment.