题意:给出N个坐标为(x,y)价值为v的目标,你有一颗边长为R的正方形炸弹,求炸弹能炸的最大价值。
思路:二维前缀和模板题目,只不过要注意的是实现细节,我们可以将这些目标(xi,yi)视为在当前点的右下角0.5个单位,然后正常处理即可。同时推荐将所有坐标+1,防止出现越界的情况。
#include <bits/stdc++.h> using namespace std; int n, R, Max; int x, y, v; int Sum[5005][5005]; int a[5005][5005]; int main(){ scanf("%d%d", &n, &R); while(n--){ scanf("%d %d %d", &x, &y, &v); x++; y++; Max = max(Max, max(x, y)); a[x][y] += v; } Max++; for(int i = 1; i <= Max; i++){ for(int j = 1; j <= Max; j++){ Sum[i][j] = Sum[i - 1][j] + Sum[i][j - 1] + a[i][j] - Sum[i - 1][j - 1]; //printf("Sum[%d][%d]:%d\n", i, j, Sum[i][j]); } } int Out = 0; for(int i = R; i <= Max; i++){ for(int j = R; j <= Max; j++){ Out = max(Out, Sum[i][j] - Sum[i-R][j] - Sum[i][j-R] + Sum[i-R][j-R]); } } printf("%d\n", Out); return 0; }