02/10/2018, 14:45
Dãy con giảm dài nhất
Nguồn đề bài http://vn.spoj.com/problems/LIS/ 1. Đề bài Dãy con giảm dài nhất Cho một dãy gồm N số nguyên (1 ≤ N ≤ 30000). Hãy tìm dãy con giảm dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint. Input Dòng đầu tiên gồm số nguyên ...
Nguồn đề bài http://vn.spoj.com/problems/LIS/
1. Đề bài Dãy con giảm dài nhất
Cho một dãy gồm N số nguyên (1 ≤ N ≤ 30000). Hãy tìm dãy con giảm dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint.
Input
- Dòng đầu tiên gồm số nguyên N.
- Dòng thứ hai gồm N số mô tả dãy.
Output
Gồm một số nguyên duy nhất là đáp số của bài toán
Example
Input:
5
3 1 2 4 0
Output:
3
2. Hướng dẫn dãy con giảm dài nhất:
Bài này như bài LIS, các bạn có thể tham khảo https://kienthuc24h.com/lis-day-con-tang-dai-nhat-ban-kho/
3. code tham khảo dãy con giảm dài nhất
const fi=';
nmax=30000;
type data=longint;
var
f:text;
A,h:array[0..nmax+1] of data;
N:data;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
read(f,a[i]);
close(f);
end;
procedure daycongiam;
var
i,j,mid,dau,cuoi,res:data;
begin
res:=1;
h[1]:=1;
for i:=2 to n do
begin
if A[h[1]]<A[i] then
h[1]:=i
else
if A[i]<a[h[res]] then
begin
inc(res);
h[res]:=i;
end
else
begin
dau:=1;
cuoi:=res;
while dau<cuoi do
begin
mid:=(dau+cuoi) div 2;
if a[h[mid]]>a[i] then
dau:=mid+1
else
cuoi:=mid;
end;
h[dau]:=i;
end;
end;
writeln(res);
end;
begin
docfile;
daycongiam;
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 | const fi='; nmax=30000; type data=longint; var f:text; A,h:array[0..nmax+1] of data; N:data; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do read(f,a[i]); close(f); end; procedure daycongiam; var i,j,mid,dau,cuoi,res:data; begin res:=1; h[1]:=1; for i:=2 to n do begin if A[h[1]]<A[i] then h[1]:=i else if A[i]<a[h[res]] then begin inc(res); h[res]:=i; end else begin dau:=1; cuoi:=res; while dau<cuoi do begin mid:=(dau+cuoi) div 2; if a[h[mid]]>a[i] then dau:=mid+1 else cuoi:=mid; end; h[dau]:=i; end; end; writeln(res); end; begin docfile; daycongiam; end. |
