题解 激光炸弹

题目链接：

AcWing
luogu

题目描述：

一颗炸弹能炸到R*R，但若目标位于爆破正方形的边上，该目标不会被摧毁。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

题解

这道题是二维前缀和的经典题，只要会公式基本没问题。
维护：f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+w[i][j];

查找：ans=max(ans,f[i][j]-f[i][j-r]-f[i-r][j]+f[i-r][j-r]);
这里由于本人太懒就不放图了

需要特别注意的是， 这道题有几个坑点：
1.边上的目标不会被摧毁，但这个条件对于以上公式并没有影响。我们把(xi,yi)(xi,yi)作为一个格子,但是实际上他们只是一个点,所以说我们不妨认为这个点就是这个格子的中心,既然如此的话我们就可以认为是(xi−0.5,yi−0.5)
2.r=c=m;，如果r=c=1就错了
3.必须

for(int i=1;i<=len;i++) 
		for(int j=1;j<=wid;j++)

如果

for(int i=0;i<=len;i++) 
		for(int j=0;j<=wid;j++)

数组会越界。所以坐标x，y都要加1，因为这道题目的坐标是从0开始的，而我们处理是从一开始的。
4.可以省略a[i][j]a[i][j]数组，将它用f[i][j]f[i][j]代替

完整代码：

#include <bits/stdc++.h>
using namespace std;
int f[5010][5010];
int main() {
	int n,r;
	int len=0,wid=0;
	cin>>n>>r;
	len=wid=r;
	int x,y,w;

	for(int i=1;i<=n;i++) {
		cin>>x>>y>>w;
		x++,y++;
		f[x][y]=w;
		len=max(len,x);
		wid=max(wid,y);
	}
	for(int i=1;i<=len;i++) {
		for(int j=1;j<=wid;j++) {
			f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[i][j];
		}
	}
	int ans=0;
	for(int i=r;i<=len;i++) {
		for(int j=r;j<=wid;j++) {
			ans=max(ans,f[i][j]-f[i][j-r]-f[i-r][j]+f[i-r][j-r]);
		}
	}
	cout<<ans;
	return 0;
}

写作时间：

2019-7-30