【题解】BZOJ P1218 【[HNOI2003]激光炸弹】

【题意】给定n个点,求一个r \times r的正方形最多覆盖多少点

这里预处理前缀和,然后暴力判断O(n^{2})

#include<cstdio>

const int MAXN = 5000 + 2;
int S[MAXN][MAXN];

inline int max(int a,int b){
	return a > b ? a : b;
}

int main(){
	int n,r;
	scanf("%d %d",&n,&r);
	
	int M = MAXN;
	M--;
	
	for(int i = 0;i < n;i++){
		int x,y,v;
		scanf("%d %d %d",&x,&y,&v);
		S[x + 1][y + 1] += v;
	}
	
	for(int i = 1;i <= M;i++){
		for(int j = 1;j <= M;j++){
			S[i][j] += S[i - 1][j];
		}
	}
	for(int i = 1;i <= M;i++){
		for(int j = 1;j <= M;j++){
			S[i][j] += S[i][j - 1];
		}
	}
	
	int ans = 0;
	for(int i = r;i <= M;i++){
		for(int j = r;j <= M;j++){
			ans = max(ans,S[i][j] + S[i - r][j - r] - S[i][j - r] - S[i - r][j]);
		}
	}
	
	printf("%d",ans);
	
	return 0;
}

 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注