Nguồn đề bài: http://www.spoj.com/PTIT/problems/VLPT12A/
1. Đề bài VLPT12A spoj
Một cửa hàng bán cơm hộp bằng cách nhận các đặt hàng qua điện thoại, sau đó sẽ giao cơm đến tận nơi. Để tăng hiệu quả kinh doanh, năm nay cửa hàng này quyết định tìm một địa điểm mới để giảm thiểu chi phí vận chuyển.
Giả sử thành phố được mô tả qua một lưới hình chữ nhật. Các địa điểm cần đến và cả cửa hàng đều là các điểm giao nhau trên lưới. Dựa trên thống kê trong năm trước, người quản lý cửa hàng biết được số yêu cầu đặt cơm trong năm. Chi phí vận chuyển từ cửa hàng đến điểm có yêu cầu được tính theo khoảng cách Manhattan, tức là tổng số đơn vị theo chiều dọc và chiều ngang tối thiểu cần đi qua trên lưới. Tất nhiên ta chỉ tính chi phí vận chuyển đến chứ không tính đoạn đường quay về.
Hãy viết chương trình xác định chi phí vận chuyển tối thiểu trong năm qua nếu đặt cửa hàng sang vị trí tối ưu nhất.
Input
Dòng 1 ghi số n là số bộ test (1<=n<=20).
Với mỗi bộ test, dòng đầu ghi hai số x,y là số cột và số dòng của lưới. 1<=x,y<=100.
y dòng tiếp theo, mỗi dòng ghi x giá trị cho biết số yêu cầu đặt cơm của mỗi điểm trong năm qua, các giá trị đều không quá 1000.
Output
Với mỗi bộ test, ghi ra màn hình một số nguyên duy nhất là chi phí vận chuyển tối thiểu trong năm qua khi đặt cửa hàng ở vị trí tối ưu.
Example
Input:
2
4 4
0 8 2 0
1 4 5 0
0 1 0 1
3 9 2 0
6 7
0 0 0 0 0 0
0 1 0 3 0 1
2 9 1 2 1 2
8 7 1 3 4 3
1 0 2 2 7 7
0 1 0 0 1 0
0 0 0 0 0 0
Output:
55
162
2. Gợi ý giải VLPT12A spoj PTIT
– Với thời gian đề cho là 10s, các bạn có thể dễ dàng giải bằng DPT N^4
3. Code tham khảo VLPT12A spoj PTIT
const fi='';
nmax=100;
type data=longint;
var
f:text;
a:array[0..nmax+1,0..nmax+1] of data;
n,x,y:data;
procedure xuli;
var i,j,u,v:data;
res,min:data;
begin
min:=high(data);
for i:=1 to x do
for j:=1 to y do
begin
res:=0;
for u:=1 to x do
for v:=1 to y do
if (u<>i) or (v<>j) then
res:=res+(abs(u-i)+abs(v-j))*a[u,v];
if res<min then
min:=res;
end;
writeln(min);
end;
procedure docfile;
var i,j,k:data;
begin
assign(f,fi); reset(f);
read(f,n);
for k:=1 to n do
begin
read(f,y,x);
for i:=1 to x do
for j:=1 to y do
read(f,a[i,j]);
xuli;
end;
close(f);
end;
begin
docfile;
end.
