洛谷题解 P2280 【[HNOI2003]激光炸弹】

一道很好的二维前缀和模板题。

什么是二维前缀和？

从这张图可以看出前缀和的求法:

Map[i][j]=Map[i-1][j]+Map[i][j-1]-Map[i-1][j-1]+Map[i][j];

这道题的代码:

#include<bits/stdc++.h>

using namespace std;

const int MAXN=5000+10;

int n,r;

int Map[MAXN][MAXN];//数组开的下

inline int read()

{

	int tot=0;

	char c=getchar();

	while(c<'0'||c>'9')

		c=getchar();

	while(c>='0'&&c<='9')

	{

		tot=tot*10+c-'0';

		c=getchar();

	}

	return tot;

}

int main()

{

	int x,y,v;

	n=read();r=read();

	for(int i=1;i<=n;i++)

	{

		x=read();y=read();v=read();

		Map[x+1][y+1]=v;

	}

	for(int i=1;i<=5000;i++)//因为地图最大是5000*5000的

		for(int j=1;j<=5000;j++)

			Map[i][j]=Map[i-1][j]+Map[i][j-1]-Map[i-1][j-1]+Map[i][j];//求出这张图的二维前缀和

	int ans=0;

	for(int i=0;i<=5000-r;i++)

		for(int j=0;j<=5000-r;j++)//放置炸弹的范围，要减去边长，否则肯定不是最优的

			ans=max(ans,Map[i+r][j+r]-Map[i][j+r]-Map[i+r][j]+Map[i][j]);//先找到爆炸范围中的总价值，再取最大值

	cout<<ans<<endl;

	return 0;

}

巴特西

洛谷题解 P2280 【[HNOI2003]激光炸弹】

最新文章

热门文章

巴特西

洛谷 题解 P2280 【[HNOI2003]激光炸弹】

最新文章

热门文章

洛谷题解 P2280 【[HNOI2003]激光炸弹】