VOI 2011 BONUS - Phần thưởng

Overview

VOI 2011 BONUS - Phần thưởng

Đề bài: https://vnoi.info/problems/BONUS/
Keywords: dp
Ngôn ngữ: C++

solution.md

Ta tính mảng F với ý nghĩa F(i,j) là tổng các phần tử trong mảng đề cho - A, trong hình chữ nhật giới hạn từ phần tử góc trên trái đến phần tử (i,j). Ta có công thức tính F(i,j) như sau:

F(i, j) = 0 khi i = 0 hoặc j = 0

F(i, j) = A(i, j) + F(i-1, j) + F(i, j-1) - F(i-1, j-1)

Từ F ta có thể tính tổng các phần tử trong hình vuông cạnh k bằng công thức:

S = F(i, j) - F(i-k, j) - F(i, j-k) + F(i-k, j-k)

Với (i, j) là toạ độ góc dưới phải của hình vuông cần tính.

Độ phức tạp: O(n^2)

main.cpp

Open in Github • Download

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, k; cin >> n >> k;
    vector< vector<int> > a(n+1, vector<int>(n+1, 0));
    int res = -1;
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) {
        int x; cin >> x;
        a[i][j] = x + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
        if (i >= k && j >= k) {
            res = max(res, a[i][j] - a[i-k][j] - a[i][j-k] + a[i-k][j-k]);
        }
    }
    cout << res << endl;
    return 0;
}