Hướng dẫn giải của Phần thưởng ý nghĩa

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, Muoikhongman, tieuc908, congtyluuthaibao1978

Editorial for dpbonus: Phần thưởng ý nghĩa

Hiểu bài toán

Bài toán yêu cầu tìm tổng giá trị lớn nhất có thể nhận được bằng cách chọn một hình vuông kích thước k x k từ một bảng n x n chứa các giá trị quà. Nói cách khác, chúng ta cần tìm một vùng hình vuông k x k trong ma trận sao cho t tổng các phần tử trong vùng đó là lớn nhất.

Các cách tiếp cận

Cách Brute Force (Tính toán trực tiếp)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    long long max_sum = 0;
    // Duyệt qua tất cả các vị trí đỉnh trái của hình vuông k x k
    for (int i = 0; i <= n - k; i++) {
        for (int j = 0; j <= n - k; j++) {
            long long current_sum = 0;
            // Tính tổng các phần tử trong hình vuông tại (i, j)
            for (int x = 0; x < k; x++) {
                for (int y = 0; y < k; y++) {
                    current_sum += a[i + x][j + y];
                }
            }
            max_sum = max(max_sum, current_sum);
        }
    }
    cout << max_sum;
    return 0;
}
  • Time Complexity: O(n^2 * k^2)
  • Space Complexity: O(n^2)

Đây là cách tiếp cận đơn giản nhất. Chúng ta duyệt qua tất cả các vị trí có thể là đỉnh trái trên của một hình vuông k x k (có (n - k + 1) * (n - k + 1) vị trí). Với mỗi vị trí, chúng ta lặp lại 2 vòng lặp bên trong để tính tổng k * k phần tử của hình vuông đó. Với mỗi tổng tính được, ta so sánh với t tổng lớn nhất hiện tại. Với ràng buộc n, k <= 1000, độ phức tạp này có thể lên tới khoảng 10^12 thao tác (nếu k gần n), dẫn đến thời gian chạy quá giới hạn (TLE).

Cách Prefix Sum (Tổng tiền tố)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    // Sử dụng mảng 1-indexed để tiện tính toán
    vector<vector<long long>> pref(n + 1, vector<long long>(n + 1, 0));

    // Xây dựng mảng tổng tiền tố
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int val;
            cin >> val;
            pref[i][j] = val + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
        }
    }

    long long max_sum = 0;
    // Duyệt qua các vị trí cuối của hình vuông k x k
    for (int i = k; i <= n; i++) {
        for (int j = k; j <= n; j++) {
            // Công thức tính tổng hình chữ nhật trong mảng tiền tố
            long long current_sum = pref[i][j] - pref[i - k][j] - pref[i][j - k] + pref[i - k][j - k];
            max_sum = max(max_sum, current_sum);
        }
    }

    cout << max_sum;
    return 0;
}
  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2)

Cách tiếp cận này sử dụng kỹ thuật mảng tổng tiền tố (Prefix Sum 2D) để tối ưu hóa việc tính tổng.

  1. Xây dựng mảng pref sao cho pref[i][j] là tổng các phần tử trong hình chữ nhật từ (1,1) đến (i,j).
  2. Để tính tổng của một hình vuông k x k có đỉnh dưới bên phải tại (i, j), ta sử dụng công thức: Tổng = pref[i][j] - pref[i-k][j] - pref[i][j-k] + pref[i-k][j-k].
  3. Độ phức tạp thời gian giảm từ O(n^2 * k^2) xuống O(n^2) vì mỗi tổng được tính trong thời gian O(1).
Cách Sliding Window (Trượt cửa sổ)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    long long max_sum = 0;

    // Bước 1: Tính tổng theo chiều dọc cho mỗi cột trong cửa sổ k
    // row_sums[r][c] lưu tổng các phần tử từ hàng r đến r+k-1 tại cột c
    vector<vector<long long>> row_sums(n - k + 1, vector<long long>(n, 0));

    // Khởi tạo cột đầu tiên cho mỗi hàng
    for (int r = 0; r <= n - k; r++) {
        long long current_col_sum = 0;
        for (int i = 0; i < k; i++) {
            current_col_sum += a[r + i][0];
        }
        row_sums[r][0] = current_col_sum;
    }

    // Tính các cột tiếp theo bằng cách trượt
    for (int r = 0; r <= n - k; r++) {
        for (int c = 1; c < n; c++) {
            row_sums[r][c] = row_sums[r][c - 1] - a[r][c - 1] + a[r + k][c - 1];
        }
    }

    // Bước 2: Duyệt qua từng hàng của row_sums và dùng sliding window theo chiều ngang
    for (int r = 0; r <= n - k; r++) {
        // Tính tổng k phần tử đầu tiên
        long long current_window_sum = 0;
        for (int c = 0; c < k; c++) {
            current_window_sum += row_sums[r][c];
        }
        max_sum = max(max_sum, current_window_sum);

        // Trượt cửa sổ sang phải
        for (int c = 1; c <= n - k; c++) {
            current_window_sum = current_window_sum - row_sums[r][c - 1] + row_sums[r][c + k - 1];
            max_sum = max(max_sum, current_window_sum);
        }
    }

    cout << max_sum;
    return 0;
}
  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2)

Phương pháp này chia bài toán thành 2 bước:

  1. Tính tổng theo chiều dọc: Duyệt qua từng hàng bắt đầu (từ 0 đến n-k), tính tổng các cột cho một cửa sổ chiều cao k. Sử dụng kỹ thuật sliding window theo chiều dọc để tính các cột tiếp theo trong O(1).
  2. Tính tổng theo chiều ngang: Trên ma trận các tổng chiều dọc đã tính được, áp dụng sliding window theo chiều ngang để tìm tổng của một hình vuông k x k. Đây là cách tiếp cận logic nhất cho các bài toán ma trận kích thước cố định.

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O(n^2 * k^2) O(n^2) Brute Force (Tính toán trực tiếp)
2 O(n^2) O(n^2) Prefix Sum (Tổng tiền tố)
3 O(n^2) O(n^2) Sliding Window (Trượt cửa sổ)

Bài học kinh nghiệm

  • Bài toán này là bài toán quy hoạch động cơ bản tìm Max Sum Submatrix với kích thước cố định.
  • Kỹ thuật Prefix Sum 2D là cách hiệu quả và phổ biến nhất để giải quyết bài toán này trong thời gian O(n^2).
  • Kỹ thuật Sliding Window (trượt cửa sổ) 2 chiều cũng cho độ phức tạp O(n^2) và là một cách tiếp cận logic để hiểu cấu trúc của t tổng.

Lỗi thường gặp

  • Lỗi truy cập ngoài biên mảng: Khi sử dụng mảng 0-indexed, điều kiện vòng lặp phải là i <= n - k thay vì i < n. Sử dụng mảng 1-indexed (khai báo kích thước n+1) giúp tránh lỗi này và làm công thức tính tổng gọn gàng hơn.
  • Sai công thức Prefix Sum: Công thức đúng để tính tổng hình chữ nhật (r1, c1) đến (r2, c2) là S[r2][c2] - S[r1-1][c2] - S[r2][c1-1] + S[r1-1][c1-1]. Việc nhầm lẫn dấu trừ/dấu cộng sẽ dẫn đến kết quả sai.
  • Kiểu dữ liệu: Tổng giá trị có thể lên tới 1000 * 1000 * 1000 = 10^9, vượt quá giới hạn của kiểu int (2*10^9). Nên sử dụng long long cho các biến lưu tổng.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.