Trở về đầu
Đề bài: Cho dãy a1,a2,..an. Hãy liệt kê tất cả các dãy con tăng dần dài nhất.
Mời các bạn download tại: Click here
const fi = 'TANGDAN.INP';
fo = 'TANGDAN.OUT';
MAXN = 10000000; // 10^7
type Mang = array [1..10] of longint; // Giai thich sau !
var n: longint;
a: array [1..MAXN] of integer;
F: array [1..MAXN] of longint;
Truoc: array [1..MAXN] of Mang;
dem: array [1..MAXN] of integer;
x: array [1..MAXN] of longint;
chiso: longint;
g: text;
procedure Nhap;
var i: longint;
begin
assign(g, fi); reset(g);
readln(g, n);
for i:= 1 to n do
read(g, a[i]);
close(g);
end;
procedure Init;
var i: longint;
begin
fillchar(dem, sizeof(dem), 0);
end;
procedure QHD;
var i, j: longint;
begin
F[1]:= 1;
for i:= 2 to n do
begin
F[i]:= 1;
for j:= 1 to i-1 do
if a[j] <= a[i] then
if F[i] < F[j] + 1 then
F[i]:= F[j] + 1;
for j:= 1 to i-1 do
if a[j] <= a[i] then
if F[i] = F[j] + 1 then
begin
inc(dem[i]);
Truoc[i][dem[i]]:= j;
// Day khong phai mang 2 chieu
end;
end;
end;
procedure InKQ;
var i: longint;
begin
for i:= chiso downto 1 do
write(g, a[x[i]], ' ');
writeln(g);
end;
procedure TruyVet(i: longint); // Thuat toan quay lui
var j: integer;
begin
for j:= 1 to dem[i] do
begin
inc(chiso);
x[chiso]:= Truoc[i][j];
if dem[Truoc[i][j]] = 0 then InKQ
else TruyVet(Truoc[i][j]);
dec(chiso); // Tra lai cau hinh
end;
end;
procedure KQ;
var imax: longint;
i, max: longint;
begin
max:= F[1];
imax:= 1;
for i:= 2 to n do
if max < F[i] then
begin
max:= F[i];
imax:= i;
end;
assign(g, fo); rewrite(g);
for i:= 1 to n do
if F[i] = max then
begin
chiso:= 1;
x[1]:= i;
TruyVet(i);
end;
close(g);
end;
BEGIN
Nhap;
Init;
QHD;
KQ;
END.