题目

题目描述

输入输出格式

输入格式：

输入文件名为input.txt

输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示 xi，yi ，vi 。

输出格式：

输出文件名为output.txt

输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。

输入输出样例

输入样例#1：

2 1

0 0 1

1 1 1

输出样例#1：

分析

看题后发现，似乎暴力不难打。看了看数据范围，喜闻乐见。

所以总得来说是个两维前缀和。

此处a[i][j]是i,j处的价值，sum[i][j]是以i,j为右下角端点，0,0为左上角端点的矩形中所有位置的总价值。

同理，最后枚举一下左上角端点的位置即可。

吐槽：题意杀了我好久，我怕是期中语文要爆0了。

代码

#include <cstdio>

#include <algorithm>

using namespace std;

int sum[5005][5005];

int main()

{

	int n,r,ans=-1;

	scanf("%d%d",&n,&r);

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

	{

		int x,y;

		scanf("%d%d",&x,&y);

		scanf("%d",&sum[x+1][y+1]);

	}

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

	{

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

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

	}

	for(int i=0;i+r<5002;i++)

	{

		for(int j=0;j+r<5002;j++)

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

	}

	printf("%d",ans);

	return 0;

}

巴特西

【BZOJ】1218: [HNOI2003]激光炸弹（前缀和）

题目