题目描述

blablabla

样例

两个要注意的点：
1.使用两个二维数组会内存不够，但是可以直接在读入数据的数组中计算二维前缀和并存放即可
2.输入数据是每个目标的价值，但是不同目标可以在同一位置，所以在读入数据可以直接进行处理存放每个位置的价值即可。

#include<cstdio>
#include<iostream>
using namespace std;
int main(){
    int n,r;
    int x,y,w;
    int s[5005][5005]={0};
    int maxx=0,maxy=0;
    scanf("%d%d",&n,&r);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&w);
        s[x+1][y+1]+=w;
        if(x+1>maxx){
            maxx=x+1;
        }
        if(y+1>maxy){
            maxy=y+1;
        }
    }
    for(int i=1;i<=maxx;i++){
        for(int j=1;j<=maxy;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
        }
    }
    int maxw=0;
    if(r>=maxx&&r>=maxy){
        printf("%d",s[maxx][maxy]);
    }
    else if(r>=maxx){
        for(int j=0;j+r<=maxy;j++){
            int now_w=s[maxx][j+r]-s[maxx][j];
            if(now_w>maxw){
                maxw=now_w;
            }
        }
    }
    else if(r>=maxy){
        for(int i=0;i+r<=maxx;i++){
            int now_w=s[i+r][maxy]-s[i][maxy];
            if(now_w>maxw){
                maxw=now_w;
            }
        }
    }
    else{
        for(int i=0;i+r<=maxx;i++){
            for(int j=0;j+r<=maxy;j++){
                int now_w=s[i+r][j+r]-s[i][j+r]-s[i+r][j]+s[i][j];
                if(now_w>maxw){
                    maxw=now_w;
                }
            }
        }
    }
    printf("%d",maxw);
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla