#前缀和 #二维前缀和

• PS:太久没写二维前缀和，有点忘了，写一个

题意

• 5000*5000的网格，有n个目标，每个目标具有价值
• 可以消除r*r个点，并获得所有消除的点的价值，求能获得的最大价值

思路

• 直接维护二维前缀和然后求答案就行
• 二维前缀和的维护是a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1]

代码

#include<bits/stdc++.h>
using namespace std;

int a[5050][5050];
int sum[5050][5050];


int main(){
    int n,r;
    cin >> n >> r;
    for(int i=0;i<n;i++){
        int x,y,v;
        cin >> x >> y >> v;
        x++;y++;
        a[x][y]+=v;
    }
    for(int i=1;i<=5001;i++){
        for(int j=1;j<=5001;j++){
            a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }
    
    int ans=0;
    for(int i=r;i<=5001;i++){
        for(int j=r;j<=5001;j++){
            ans=max(ans,a[i][j]-a[i-r][j]-a[i][j-r]+a[i-r][j-r]);
        }
    }
    cout << ans << endl;
    return 0;
}