Bài 2: Dầu
khí (Đề thi Tin học 10 – Olympic 30/4/2013)
Một tàu thăm dò
dầu khí của công ty Bình Minh đã xác định được một khu vực A có dạng hình chữ
nhật có chiều dài M km, chiều rộng N km, chia thành MxN ô vuông bằng nhau, mỗi
một ô của khu vực này chứa một lượng dầu có giá trị A[i,j]. Công ty Bình Minh
muốn giữ lại một khu vực hình vuông chiều dài K km. còn các khu vực khác thì
bán đi.
Yêu cầu:
Hãy xác định hình vuông chiều dài K có tổng giá trị dầu khí lớn nhất?
Dữ liệu vào:
Daukhi.inp:
- Dòng đầu tiên chứa 3 số nguyên
M, N, K (M, N ≤ 1000; K ≤ min(M,N)) các số cách nhau bởi 1 khoảng trắng.
- Dòng thứ i trong M dòng tiếp
theo chứa N số nguyên, số thứ i là A[i, j] ≤ 1000.
Dữ liệu ra:
Daukhi.out: một số nguyên duy nhất chứa tổng giá trị lớn nhất của khu vực cần
giữ lại.
Daukhi.inp
|
Daukhi.out
|
4 3 2
1 2 3
1 1 1
1 1 1
1 1 1
|
7
|
ĐÁP ÁN - HƯỚNG DẪN GIẢI
Cách 1: O(N^4)
Procedure isOK(i, j:
integer); //O(N^2)
Var p, q: integer; S:longint;
Begin
S:=0;
For
p:=1 to K do
For q:=1 to K do
S:= S + a[i+p-1, j+q-1];
If s>max then max:=S;
End;
Procedure Solve;
//O(N^2)
Var i, j: integer;
Begin
Max:=0;
For i:=1 to
M-K+1 do
For j:=1 to N – K + 1 do
isOK(i,j);
End;
Cách 2: O(N^3)
A
|
1
|
2
|
3
|
1
|
1
|
2
|
3
|
2
|
1
|
1
|
1
|
3
|
1
|
1
|
1
|
4
|
1
|
1
|
1
|
Gọi Sum[i,j] là tổng của hình
vuông K có góc trái trên là (i,j).
Procedure isOK(i, j:
integer); //O(N)
Var p, q: integer;
Begin
Sum[i,j]:=Sum[i-1,j];
For
p:=1 to K do
Begin
Sum[i,j]:= Sum[i,j] + a[i+K-1, p+j-1];
Sum[i,j]:= Sum[i,j] – a[i-1, p+j-1];
End;
If sum[i,j]>max then max:=Sum[i,j];
End;
Cách 3: O(N^2)
Procedure isOK(i, j:
integer); //O(1)
Var p, q: integer;
Begin
S[i,j]:=S[i-1,j] + S[i, j-1] – S[i-1, j-1] + a[i-1,j-1] – a[i-1, j+K-1] –
a[i+K-1, j-1] + a[i+K-1, j+K-1] ;
If sum[i,j]>max then max:=Sum[i,j];
End;
Với O(N^2) thì có thể chạy được với
N ~ 30 000.
Không có nhận xét nào:
Đăng nhận xét