02/10/2018, 13:54
LIS spoj – Dãy con tăng dài nhất (bản khó)
Nguồn đề bài http://vn.spoj.com/problems/LIS/ Đề bài LIS Spoj Tìm dãy con tăng dài nhất, số lượng phần tử tối đa 30000. In ra số lương lớn nhất có thể Input: 5 2 1 4 3 5 Output: 3 Link nộp bài: http://vn.spoj.com/problems/LIS/ Code Lis spoj Pascal const fi= ...
Nguồn đề bài http://vn.spoj.com/problems/LIS/
Đề bài LIS Spoj
Tìm dãy con tăng dài nhất, số lượng phần tử tối đa 30000. In ra số lương lớn nhất có thể
Input:
5
2 1 4 3 5
Output:
3
Link nộp bài:
http://vn.spoj.com/problems/LIS/
Code Lis spoj Pascal
const fi= ';
fo= ';
maxd= 30001;
var a: array[0..maxd] of longint;
l: array[0..maxd] of integer;
n: longint;
d: longint;
procedure mofile;
var i,j:integer;
begin
assign(input,fi);reset(input);
assign(output,fo);rewrite(output);
end;
procedure dongfile;
begin
close(input);close(output);
end;
procedure nhap;
var i:longint;
f:text;
begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
read(f,a[i]); close(f);
end;
procedure xuli;
var i,k,dau,cuoi:longint;
begin
l[1]:=1;d:=1;
for i:=2 to n do
begin
if a[i]>a[l[d]] then
begin
inc(d);
l[d]:=i;
end
else
begin
dau:=1;
cuoi:=d;
while dau<cuoi do
begin
k:=(dau+cuoi) div 2;
if a[l[k]]<a[i] then
dau:=k+1
else
cuoi:=k;
end;
l[dau]:=i;
end;
end;
end;
procedure xuat;
begin
write(d);
end;
begin
nhap;
xuli;
xuat;
end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | const fi= '; fo= '; maxd= 30001; var a: array[0..maxd] of longint; l: array[0..maxd] of integer; n: longint; d: longint; procedure mofile; var i,j:integer; begin assign(input,fi);reset(input); assign(output,fo);rewrite(output); end; procedure dongfile; begin close(input);close(output); end; procedure nhap; var i:longint; f:text; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do read(f,a[i]); close(f); end; procedure xuli; var i,k,dau,cuoi:longint; begin l[1]:=1;d:=1; for i:=2 to n do begin if a[i]>a[l[d]] then begin inc(d); l[d]:=i; end else begin dau:=1; cuoi:=d; while dau<cuoi do begin k:=(dau+cuoi) div 2; if a[l[k]]<a[i] then dau:=k+1 else cuoi:=k; end; l[dau]:=i; end; end; end; procedure xuat; begin write(d); end; begin nhap; xuli; xuat; end. |
