题解 | #[HNOI2003]激光炸弹#

思路

考虑维护一个二维前缀和，每次枚举时仅需枚举炸弹区域的左上角坐标即可， 右下角坐标可通过R得出。

代码

#include <bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0)
using namespace std;
const int N = 5010;
int Gsum[N][N];

int main(){
    ios;
    int n,R,ans = 0;
    cin>>n>>R;
    //获取各目标的价值(坐标处理)
    for(int i = 1;i <= n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        Gsum[a+1][b+1] = c;
    }
    //求二维前缀和
    for(int i = 1;i < N;i++)
        for(int j = 1;j < N;j++){
            Gsum[i][j] += (Gsum[i-1][j] + Gsum[i][j-1] - Gsum[i-1][j-1]);
        }
    //枚举区域左上角（根据R可得右下角），注意边界判断
    R--;
    for(int x = 1;x < N;x++){
        for(int y = 1;y < N;y++){
            if(x+R < N && y+R < N){
                int tmp = Gsum[x+R][y+R] - Gsum[x+R][y-1] - Gsum[x-1][y+R]
                    + Gsum[x-1][y-1];
                //维护一个总价值最大值
                ans = max(ans,tmp);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}