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: Có n lọ hoa sắp thẳng hàng và k bó hoa được đánh số thứ tự từ nhỏ đến lớn. Cần cắm k bó hoa trên vào n lọ sao cho hoa có số thứ tự nhỏ phải đứng trước hoa có số thứ tự lớn. Giá trị thẩm mỹ tương ứng khi cắm hoa i vào lọ thứ j là v(i,j) Hãy tìm 1 cách cắm sao cho tổng giá trị thẫm mỹ là lớn nhất. Chú ý rằng mỗi bó hoa chỉ được cắm vào 1 lọ và mỗi lọ cũng chỉ cắm được 1 bó hoa.

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

const fi = 'LOHOA.INP';
      fo = 'LOHOA.OUT';
      MAXN = 1000;
      MAXK = 1000;
var n, k: integer;
    v: array [1..MAXK, 1..MAXN] of integer;
    L: array [1..MAXK, 1..MAXN] of integer;
    f: text;

procedure Nhap;
var i, j: integer;
begin
        assign(f, fi); reset(f);
        readln(f, n, k);
        // v[i, j] la gia tri tham my lon nhat khi cam hoa i vao lo j
        for i:= 1 to k do
                for j:= 1 to n do read(f, v[i, j]);
        close(f);
end;

function sum(i: integer): integer;
var s, t: integer;
begin
        s:= 0;
        for t:= 1 to i do
                s:= s + v[t, t];
        exit(s);
end;

function max(a, b: integer): integer;
begin
        if a > b then exit(a)
                else exit(b);
end;

procedure QHD;
var i, j, t: integer;
begin
        // Xay dung bai toan con co ban
        // Goi L[i, j] la gia tri tham my lon nhat khi xep 1..i hoa vao
        // 1..j lo
        L[1, 1]:= v[1, 1];
        for j:= 2 to n do
        begin
                L[1, j]:= -1;
                for t:= 1 to j do
                        if L[1, j] < v[1, t] then
                                L[1, j]:= v[1, t];
        end;

        for i:= 2 to k do
                for j:= 1 to n do
                    if i = j then L[i, j]:= sum(i)
                    else
                    begin
                        if i > j then L[i, j]:= -1
                           else // i < j
                                L[i, j]:= max(L[i-1, j-1] + v[i, j],
                                              L[i, j-1]);
                    end;
end;

procedure TruyVet(i, j: integer);
var t: integer;
begin
        if i = 1 then
        begin
                if j = 1 then
                begin
                        writeln(f, 'Chon hoa 1 cam vao lo 1');
                        exit;
                end;
                // j > 1
                for t:= 1 to j do
                        if L[i, j] = v[1, t] then
                        begin
                                writeln(f, 'Chon hoa 1 cam vao lo ', t);
                                exit;
                        end;
        end;


        if j = 1 then exit;

        if L[i, j] = L[i-1, j-1] + v[i, j] then
        begin
                TruyVet(i-1, j-1);
                writeln(f, 'Chon hoa ', i, ' cam vao lo ', j);
        end
                else TruyVet(i, j-1);
end;

procedure InKQ;
begin
        assign(f, fo); rewrite(f);
        writeln(f, L[k, n]);
        if L[k, n] = -1 then writeln(f, 'Khong co cach cam hop ly')
                else TruyVet(k, n);
        close(f);
end;

BEGIN
        Nhap;
        QHD;
        InKQ;
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