HỌC TIN CÙNG THỦ KHOA

Đề bài: Cho một tam giác gồm các số nguyên không âm. Hãy tính tổng lớn nhất các số trên đường đi từ đỉnh tam giác xuống một điểm nào đó ở đáy tam giác nào đó. Tại mỗi ô ta chỉ có đi thẳng xuống, sang ô bên trái hoặc bên phải.

Mời các bạn download tại: Click here

const fi = 'TAMGIAC.INP';
      fo = 'TAMGIAC.OUT';
      MAXM = 1000;
      MAXN = 1000;

var g : text;
    N, M : integer;
    a: array [1..MAXM, 1..MAXN] of integer;
    F: array[1..MAXM, 0.. MAXN] of integer;

procedure Nhap;
var i, j : integer;
begin
    assign(g, fi); reset(g);
    readln(g, N);
    for i:=1 to N do
       for j := 1 to i do  read(g, a[i,j]);
end;

procedure Init;
begin
	fillchar(F, sizeof(F), 0);
end;

function Max2(x, y : integer) : integer;
var max : integer;
begin
    if x < y then exit(y) else exit(x);
end;

procedure QHD;
var i, j: integer;
begin
    F[1, 1] := a[1, 1];

    for i:= 2 to N do
       for j:=1 to N do
            F[i, j] := Max2(F[i-1, j-1], F[i-1,j]) + a[i, j];
end;

procedure TruyVet(i, j : integer);
begin
        if i = 1 then
                write(g, '(', i, ', ' , j, ') ')

        else  // i > 1
        begin
                if F[i, j] = F[i-1, j-1] + a[i, j] then
                        TruyVet(i-1, j-1)
                else   TruyVet(i-1, j);

                write(g, ' -> (', i, ', ', j, ')');
        end;
end;

procedure InKQ;
var max, j, k: integer;
begin
        assign(g, fo); rewrite(g);
        max:= -1;
        for j:= 1 to N do
                if max < F[N, j] then
                begin
                        max:= F[N, j];
                        k:= j;
                end;
        writeln(g, max);
        TruyVet(N, k);
        close(g);
end;

BEGIN
        Nhap;
        Init;
        QHD;
        InKQ;

END.