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.
