[pascal]Phần thưởng

[rabbit.thuy]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Các phần thưởng được bố trí trên 1 bẳng vuông kích thước nxn có dạng 1 lưới ô vuông kích thước đơn vị. trên ô i,j có 1 món quà có giá trị a[i,j]. Để nhận được thưởng, cho phép chọn hình vuông kích thước kxk chiếm trọn 1 số ô của bảng và nhận các phần quà trong hình vuông đó. (n\leq1000, \frac{n}{3}\leqk\leqn).
Lập trình in số điểm lớn nhất có thể nhận đc.
INP:
4 3 (n=4,k=3)
1 9 1 1
9 9 9 9
1 9 9 9
1 9 9 14
OUT: 86

 

[mikelhpdatke]

Cách đơn giản nhất là duyệt , lấy 2 biến chạy, duyệt rồi kiểm tra tính tổng, nếu tổng >tongmax thì tongmax:=tong đang tính
Còn thuật khác mình chưa nghĩ ra

 

[hgminh95]

Gọi f[i, j] là tổng các số trong hcn từ ô (1, 1) -> ô (i, j)
Khởi tạo f[i, j] như sau
f[0, i] = f[i, 0] = 0 với mọi i
f[i, j] = f[i - 1, j] + f[i, j - 1] + a[i, j] - f[i - 1, j - 1] với i, j >= 1

Sau khi đã tính được mảng f[i, j], để tính tổng các số trong 1 hình vuông bất kỳ chỉ mất O(1), bạn vẽ ra giấy là thấy ngay công thức => Duyệt O(n^2) hết tất cả các hình vuông là được