. DẴY ĐƠN ĐIỆU TĂNG DÀI NHẤT
Cho dãy số nguyên dương a = (a1, a2, …, an) (1 n 10000; 1 ai 10000)
Hãy tìm dãy chỉ số dài nhất i1, i2, …, ik¬ thoả mãn:
• 1 i1 < i2 < ... < ik n
• ai¬¬1 < ai2 < ... < aik
Dữ liệu: Vào từ file văn bản INCSEQ.INP
• Dòng 1: Chứa số n
• Dòng 2: Chứa n số a1, a2, ..., an
Kết quả: Ghi ra file văn bản INCSEQ.OUT
• Dòng 1: Ghi số k
• Dòng 2: Ghi k số i1, i2, ..., ik
Các số trên một dòng của Input/Output file cách nhau ít nhất một dấu cách
Ví dụ:
INCSEQ.INP INCSEQ.OUT
8
1 2 8 9 5 6 7 9 6
1 2 5 6 7 8
làm nhanh cho ctln
Program DayDonSDieuTangDayNhat;
Uses crt;
const
max = 6000;
var
a, l, t, StartOf: array[0..max + 1] of Integer;
n, m: Integer;
procedure Nhap;
var
i: Word;
fi, fo: Text;
begin
Assign(fi, ‘INCSEQ.INP’);
Reset(fi);
ReadLn(fi, n);
for i := 1 to n do Read(fi, a[i]);
Close(fi);
end;
procedure Init;
begin
a[0] := -32768;
a[n + 1] := 32767;
m := 1;
L[n + 1] := 1;
StartOf[1] := n + 1;
end;
function Find(i: Integer): Integer;
var
inf, sup, median, j: Integer;
begin
inf := 1;
sup := m + 1;
repeat
median := (inf + sup) div 2;
j := StartOf[median];
if a[j] > a[i] then inf := median
else sup := median;
until inf + 1 = sup;
Find := StartOf[inf];
end;
procedure Optimize;
var
i, j, k: Integer;
begin
for i := n downto 0 do
begin
j := Find(i);
k := L[j] + 1;
if k > m then
begin
m := k;
StartOf[k] := i;
end
else
if a[StartOf[k]] < a[i] then StartOf[k] := i;
L[i] := k;
T[i] := j;
end;
end;
procedure Result;
var
f: Text;
i: Integer;
begin
Assign(fo, ‘INCSEQ.OUT’);
Rewrite(fo);
WriteLn(fo, m – 2);
i := T[0];
while i <> n + 1 do
begin
WriteLn(fo, ‘a[‘, i, ‘] = ‘, a[i]);
i := T[i];
end;
Close(fo);
end;
begin
Nhap;
Init;
Optimize;
Result;
end.
var a,nho,luu:array[0..10000] of word;
i,j,n,nho1:word;
max:word;
f1,f2:text;
const fi=’INCSEQ.INP’;
fo=’INCSEQ.OUT’;
procedure luukq;
var j1:word;
begin
for j1:=1 to max do
begin
luu[j1]:=nho[j1];
end;
end;
procedure try(i,dem:word);
var i1,j1:word;
begin
if i<=n then
for i1:=i to n do
if a[i1]>nho[dem-1] then
begin
nho[dem]:=a[i1];
try(i1+1,dem+1);
if dem>max then
begin
max:=dem;
luukq;
end;
end;
end;
begin
assign(f1,fi);reset(f1);
assign(f2,fo);rewrite(f2);
repeat
readln(f1,n);
until (1<=n) and (n<=10000);
fillchar(nho,sizeof(nho),0);
for i:=1 to n do read(f1,a[i]);
max:=0;
try(1,1);
writeln(f2,max);
for i:=1 to max do write(f2,luu[i],’ ‘);
close(f1);close(f2);
end.