Dãy con giảm dài nhất

Nguồn đề bài http://vn.spoj.com/problems/LIS/

Nội dung bài viết

1. Đề bài Dãy con giảm dài nhất
2. Hướng dẫn dãy con giảm dài nhất:
3. code tham khảo dãy con giảm dài nhất

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.

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;

writeln(res);

end;

begin

docfile;

daycongiam;

end.

1. Đề bài Dãy con giảm dài nhất

Input

Output

Example

2. Hướng dẫn dãy con giảm dài nhất:

3. code tham khảo dãy con giảm dài nhất

Bài viết liên quan

Trả lời Hủy