02/10/2018, 13:55
YB_KT2B2 spoj THPTCBT – 20686. Phần thưởng
Nguồn đề bài http://www.spoj.com/THPTCBT/problems/YB_KT2B2/ Đề bài YB_KT2B2 spoj TIMBERSAW oai hùng ngày nào nay đã trở thành bác bảo vệ của rừng Radiant (có dạng hình chữ nhật kích thước MxN). Để đền đáp công lao to lớn của TIMBERSAW, Chúa đất cho phép anh chọn một khu rừng hình ...
Nguồn đề bài http://www.spoj.com/THPTCBT/problems/YB_KT2B2/
Đề bài YB_KT2B2 spoj
TIMBERSAW oai hùng ngày nào nay đã trở thành bác bảo vệ của rừng Radiant (có dạng hình chữ nhật kích thước MxN). Để đền đáp công lao to lớn của TIMBERSAW, Chúa đất cho phép anh chọn một khu rừng hình chữ nhật có kích thước k*k, có các cạnh song song với các bìa rừng và Chúa đất chỉ cho phép anh khai thác cây trên đường biên của khu rừng đó. Biết giá trị của mỗi cây trong khu rừng Radiant là a[i,j] nguyên.
Bạn hãy giúp TIMBERSAW chọn một khu rừng có giá trị cao nhất mà vẫn thỏa mãn yêu cầu của Chúa đất.
Input
- Dòng 1: Gồm 3 số m, n , k ( 0< k ≤ min(m,n); m,n ≤ 1000).
- m dòng sau, mỗi dòng n số nguyên là giá trị của mỗi cây trong khu rừng.
Output
- Một số duy nhất là giá trị cao nhất mà TIMBERSAW có thể nhận được.
Example
Input:
4 4 3
3 4 5 -5
-7 0 7 2
3 -7 6 -4
1 -6 -3 -5
Output:
14
Hướng dẫn giải YB_KT2B2 spoj
Gợi ý: cách làm tương tự như bài BONUS, bạn có thể search trên trang web.
Code tham khảo YB_KT2B2 spoj
const fi=';
nmax=1000;
type data=longint;
var
f:text;
A:array[0..nmax+1, 0..nmax+1] of int64;
n,m,k:data;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,m,n,k);
for i:=0 to m+1 do
a[i,0]:=0;
for j:=0 to n+1 do
a[0,j]:=0;
for i:=1 to m do
for j:=1 to n do
begin
read(f,a[i,j]);
a[i,j]:=a[i-1,j]+a[i,j-1]-a[i-1,j-1]+a[i,j];
end;
close(f);
end;
function max(a,b:int64):int64;
begin
if a>b then exit(a);
exit(b);
end;
procedure QHD;
var i,j,bt:data;
res:int64;
begin
res:=low(int64);
for i:=k to m do
for j:=k to n do
begin
bt:=A[i,j]-a[i-k,j]-a[i,j-k]+a[i-k,j-k];
if k>2 then
bt:=bt-(A[i-1,j-1]-a[i-k+1,j-1]-a[i-1,j-k+1]+a[i-k+1,j-k+1]);
res:=max(res,bt);
end;
writeln(res);
end;
begin
docfile;
QHD;
end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | const fi='; nmax=1000; type data=longint; var f:text; A:array[0..nmax+1, 0..nmax+1] of int64; n,m,k:data; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,m,n,k); for i:=0 to m+1 do a[i,0]:=0; for j:=0 to n+1 do a[0,j]:=0; for i:=1 to m do for j:=1 to n do begin read(f,a[i,j]); a[i,j]:=a[i-1,j]+a[i,j-1]-a[i-1,j-1]+a[i,j]; end; close(f); end; function max(a,b:int64):int64; begin if a>b then exit(a); exit(b); end; procedure QHD; var i,j,bt:data; res:int64; begin res:=low(int64); for i:=k to m do for j:=k to n do begin bt:=A[i,j]-a[i-k,j]-a[i,j-k]+a[i-k,j-k]; if k>2 then bt:=bt-(A[i-1,j-1]-a[i-k+1,j-1]-a[i-1,j-k+1]+a[i-k+1,j-k+1]); res:=max(res,bt); end; writeln(res); end; begin docfile; QHD; end. |
