Tìm tổng các lớp ô vuông lớn nhất

Cho lưới ô vuông kích thước NxN, tại ô (i,j) ghi số nguyên a[i,j].Người ta chọn một hình vuông có kích thước KxK (1 ≤ K ≤ N). Sau đó cắt hình vuông này thành từng lớp có độ dày 1 đơn vị (có dạng hình vuông rỗng ruột) có kích thước lần lượt KxK, (K-1)x(K-1)… Bạn phải chọn các lớp không liên tiếp, bắt đầu từ lớp ngoài cùng (lớp có kích thước KxK) trở vào và tổng các ô trong các lớp bạn chọn là số điểm bạn thu được.
Ví dụ, ta sẽ chọn hình vuông kích thước 4x4 như hình bên. Khi cắt hình vuông này ta chỉ được 2 lớp và tổng các ô được chọn theo cách trên là 25.
image

Yêu cầu: Tìm tổng điểm lớn nhất mà bạn có thể có được.

Dữ liệu: Vào từ tệp “BONUS.INP” gồm:

  • Dòng 1: Ghi số nguyên dương N (N ≤ 100).
  • N dòng tiếp theo, mỗi dòng ghi N số nguyên a[i,j] (|a[i,j]| ≤ 109).

Kết quả: Ghi ra tệp “BONUS.OUT”số nguyên duy nhất là kết quả tìm được.

BONUS.INP
1 -1 3 -2 1
-5 6 -3 3 -2
6 1 2 1 1
-4 -2 8 7 5
-6 0 4 -1 1

BONUS.OUT
25

Ý tưởng của em là dùng tổng tích lũy nhưng có một vấn đề là khi xét các hình vuông con bên trong e vẫn chưa có định hướng gì ạ

Bạn có thể tính được tổng giá trị của hình vuông từ mảng 2 chiều chưa?
Giờ bạn chỉ bí là làm sao để liệt kê hết các hình vuông có trong mảng thôi, duyệt trâu thôi. Chắc cũng 3 vòng lặp lồng nhau.
1 cho giá trị k, 1 cho dòng, 1 cho cột trong bảng.

4 Likes

Bạn phải chọn các lớp không liên tiếp, bắt đầu từ lớp ngoài cùng (lớp có kích thước KxK) trở vào và tổng các ô trong các lớp bạn chọn là số điểm bạn thu được.

Nó còn dính cái yêu cầu này nữa ý ạ. Nếu tìm mỗi hình vuông có tổng lớn nhất thì dễ rồi ạ :frowning:

Bạn cần làm được bài tổng dãy con không liên tiếp cực đại :smiley: rồi mới tìm hiểu cấu trúc thật sự của cái đề này.

4 Likes

Dạ để em tìm kiếm thử ạ :3

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?