LIS – SPOJ

Đề bài:

Thuật toán:

  • for lồng với chặt nhị phân mất tốc độ O(n)log(n)
  • các bạn xem code thắc mắc đâu thì hỏi thêm nha

Code:

program         LIS;
var     a,l:array[1..30000] of longint;
        d,i,dau,cuoi,mid,n:longint;
begin
        readln(n);
        for i:=1 to n do read(a[i]);
        d:=1;
        l[1]:=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
                                                        mid:=(dau+cuoi) div 2;
                                                        if a[i]>a[l[mid]] then dau:=mid+1
                                                        else cuoi:=mid-1; 
                                                end;
                                        l[dau]:=i;
                                end;
                end;
        write(d);
end.

LIQ – spoj

Đề bài:

Thuật toán:

  • for 2 vòng lồng nhau để kiểm tra điều kiện nếu thoả mãn thì tăng biến đếm lên nếu không thì giữ nguyên

Code:

program      LIQ;
var    n,res,i,j:longint;
a,f:array[1..1009] of longint;
begin
readln(n);
res:=0;
for i:=1 to n do
begin
read(a[i]);
f[i]:=1;
for j:=1 to i-1 do
if (a[i]>a[j]) and (f[j]+1>f[i]) then f[i]:=f[i]+1;
if f[i]>res then res:=f[i];
end;
writeln(res);
end.