Trở về đầu

foto1 foto2 foto3 foto4 foto5
Giảng viên
Nguyễn Tô Sơn - Thủ khoa Đại học Sư phạm Hà Nội
ĐT: 091.333.2869

HỌC TIN CÙNG THỦ KHOA

Thành công không phải đích đến, mà là cả một hành trình

Tìm kiếm

Đề 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.

Giảng viên Nguyễn Tô Sơn, Thủ khoa Đại học Sư phạm Hà Nội. Điện thoại: 091.333.2869