程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj1218【HNOI2003】激光炸彈

bzoj1218【HNOI2003】激光炸彈

編輯:關於C++

Description

一種新型的激光炸彈,可以摧毀一個邊長為R的正方形內的所有的目標。現在地圖上有n(N<=10000)個目標,用整數Xi,Yi(其值在[0,5000])表示目標在地圖上的位置,每個目標都有一個價值。激光炸彈的投放是通過衛星定位的,但其有一個缺點,就是其爆破范圍,即那個邊長為R的正方形的邊必須和x,y軸平行。若目標位於爆破正方形的邊上,該目標將不會被摧毀。 0

Input

輸入文件的第一行為正整數n和正整數R,接下來的n行每行有3個正整數,分別表示

Output

輸出文件僅有一個正整數,表示一顆炸彈最多能炸掉地圖上總價值為多少的目標(結果不會超過32767)。

Sample Input

2 1
0 0 1
1 1 1

Sample Output

1

HINT

Source

Dp

這是一道大水題,暴力枚舉+二維前綴和。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 5005
using namespace std;
int n,r,x,y,z,ans=0;
int s[maxn][maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	n=read();r=read();
	F(i,1,n)
	{
		x=read()+1;y=read()+1;z=read();
		s[x][y]+=z;
	}
	F(i,1,5001) F(j,1,5001) s[i][j]+=s[i][j-1];
	F(i,1,5001) F(j,1,5001) s[i][j]+=s[i-1][j];
	F(i,r,5001) F(j,r,5001)
	{
		int tmp=s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r];
		ans=max(ans,tmp);
	}
	printf("%d\n",ans);
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved