1 一枚炸弹最多摧毁的格点数:R×R
2 简化:R大很多和大一点是一样 所以最大取到5001 R=min(5001,R)
3 R*R 的格点里 总和最大的子矩阵—(n-R+1)(m-R+1)?
4 矩阵里的价值总和 用二维前缀和 容斥原理
可以只枚举右下角(格点)
==Sx2y2 - Sx1-1y2 - Sx2y1-1 - Sx1-1y1-1
左上角为x-R+1,y-R+1
所以
== Sxy - Sx-Ry - Sxy-R - Sx-Ry-R
5预处理前缀和
Sxy+=Sx-1y+Sxy-1-Sx-1y-1
题目代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=5010;
int s[N][N];
int main(){
int cnt,R;
cin>>cnt>>R;
R=min(5001,R);
int m=R,n=R;
while(cnt--){
int x,y,w;
cin>>x>>y>>w;
x++,y++;//令所有坐标都大于等于1
s[x][y]+=w;//题目中说不同的目标可以在同一点,因此一个点的价值也可能不止一个,需要累加起来
n=max(x,n);//n为最大横坐标
m=max(y,m);//m为最大纵坐标
}
//预处理前缀和
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
//求R*R内价值数 枚举右下角 求最小值
int res=0;
for(int i=R;i<=n;i++)
for(int j=R;j<=m;j--){
int w=s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R];
res=max(w,res);
}
cout<<res<<endl;
return 0;
}