题目描述

输入n个坐标(x,y)与其对应的分数(v)，求边长为r的正方形区域内最大的分数和

数据范围：1<=n<=10^4, 0<=x,y<=5000, 0<=r<=5000, 1<=v<=1000

分析

使用二维前缀和的方法,对于所求的边长为r的正方形的和为f[x][y] - f[x-r][y] - f[x][y-r] + f[x-r][y-r]

ac代码

具体细节见注释

ps:关于前缀和几种计算方式以及对于高维时的优劣，包括拓展到二维差分，可以查看该篇文章，我看完受益匪浅（膜拜大佬orz）

#include<bits/stdc++.h>
using namespace std;
#define MAX 5001//因为坐标从0开始，所以为了方便计算，所有坐标加1
int main()
{
    int r = 0, n = 0, x = 0, y = 0, v = 0;
    int f[MAX+1][MAX+1] = { 0 };//数组开大放越界
    memset(f, 0, sizeof(f));
    scanf("%d %d", &n, &r);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d %d", &x, &y, &v);
        f[x+1][y+1] +=v;//不知道为什么，在洛谷中直接使用'='赋值会有一个测试点无法通过，二编：破案了，洛谷题目写了可能同一点会有多个不同的目标，所以需要加等
    }
    int ans = 0, sum = 0;
  //第一种求二维前缀和的方法
    /*
    for (int i = 1; i <= MAX; i++)
    {
        for (int j = 1; j <= MAX; j++)
        {
            f[i][j] = f[i][j] + f[i - 1][j] +f[i][j - 1] -  f[i - 1][j - 1];
        }
    }
    */
  //第二种求二维前缀和的方法
    for (int i = 1; i <= MAX; i ++)
		for (int j = 1; j <= MAX; j ++) f[i][j] += f[i][j - 1];
	for (int j = 1; j <= MAX; j ++)
		for (int i = 1; i <= MAX; i ++) f[i][j] += f[i - 1][j];
  
  
  //求出最大值
    for(int i = r;i <= MAX;i++)
    {
        for(int j = r;j <= MAX ; j++)
        {
            sum = f[i][j] - f[i - r][j] - f[i][j - r] + f[i - r][j - r];
            ans = max(ans , sum);
        }
    }
    printf("%d", ans);
    return 0;
}

总结

这题实际上学会了二维前缀和还是挺简单的，但是我中间调整数据，以及理解题目花了不少时间。