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

题目链接：

https://www.luogu.org/problemnew/show/P2280
思路：

简单的二维前缀和，最后扫描一遍求

max(ans,f[i][j]+f[i-r][j-r]-f[i-r][j]-f[i][j-r]);

两个操作时间复杂度都是N方
注意细节：
- mx,my初始值赋值为边长，否则会有一个点WA
- x,y因为从0开始，都加1方便处理
- 第二遍扫描时，从r开始扫描
- 因为v值较小，可以用short，不过我很好奇为什么不能用char

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

using namespace std;

const int maxn=5005;

int n,r;

short int map[5005][5005];

int f[5005][5005],mx=0,my=0;

template <class T>void read(T & x)

{

	int ne=0;char c;

	while(!isdigit(c=getchar()))ne=c=='-';

	x=c-48;

	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;

	x=ne?-x:x;

	return;

}

int main()

{

	int x,y,v,ans=0;

	read(n),read(r);mx=r,my=r;

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

	{

		read(x),read(y),read(v);

		x++,y++;

		map[x][y]=v;

		mx=max(mx,x),my=max(my,y);

	}

	for(register int i=1;i<=mx;i++)

		for(register int j=1;j<=my;j++)

			f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+map[i][j];

	for(register int i=r;i<=mx;i++)

		for(register int j=r;j<=my;j++)

			ans=max(ans,f[i][j]+f[i-r][j-r]-f[i-r][j]-f[i][j-r]);

	printf("%d\n",ans);

	return 0;

}

巴特西

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

最新文章

热门文章