C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

二维前缀和

$1、预处理一下矩阵中每个点的最大价值$

$2、枚举所有边长是R的矩形，枚举(i, j)为右下角，取最大值即可$

$图解：$

$时间复杂度：O(n^2)$

$空间复杂度：$

$int \ s[N][N], N为5000，那么会占据 5000 * 5000 * 4 = 1 * 10^8个 Byte，$

$1MB = 1024 KB = 1024 * 1024 Byte = 1 * 10^6 Byte,$

$总共占据了 10^8 / 10^6 = 100 MB$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5010;

int n, m;
int s[N][N];

int main() {
    int cnt, R;
    cin >> cnt >> R;
    R = min(5001, R);

    n = m = R;
    while (cnt --) {
        int x, y, w;
        cin >> x >> y >> w;
        x ++, y ++;
        n = max(x, n), m = max(y, m); // 确定该矩阵的边界
        s[x][y] += w;
    }

    // 预处理前缀和
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    int res = 0;

    // 枚举所有边长是R的矩形，枚举(i, j)为右下角
    for (int i = R; i <= n; i ++) 
        for (int j = R; j <= m; j ++)
            res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);

    cout << res;

    return 0;
}

$\small{分享：}$

$\large\color{blue}{— > C/C++输入字符串}$