Trở về đầu
Đề 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.