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.
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