点击打开poj 2029
思路: 简单的二维树状数组
分析:
1 题目给定一个人h*w的矩阵,给定n个点表示该点上面有柿子树,求给定一个t*s的矩阵的最多的柿子树的个数
2 简单的二维树状数组,加入一个点的时候更新树状数组
3 题目的范围最大为100,很明显就是要暴力枚举起点,然后求最大值即可
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 110;
int n , w , h;
int treeNum[MAXN][MAXN];
int lowbit(int x){
return x&(-x);
}
void add(int x , int y , int val){
for(int i = x ; i < MAXN ; i += lowbit(i))
for(int j = y ; j < MAXN ; j += lowbit(j))
treeNum[i][j] += val;
}
int getSum(int x , int y){
int sum = 0;
for(int i = x ; i > 0 ; i -= lowbit(i))
for(int j = y ; j > 0 ; j -= lowbit(j))
sum += treeNum[i][j];
return sum;
}
int solve(int x , int y){
int ans = 0;
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
int sum = getSum(i+x-1 , j+y-1);
sum -= getSum(i-1 , j+y-1);
sum -= getSum(i+x-1 , j-1);
sum += getSum(i-1 , j-1);
ans = max(ans , sum);
}
}
return ans;
}
int main(){
int x , y;
while(scanf("%d" , &n) && n){
scanf("%d%d" , &w , &h);
memset(treeNum , 0 , sizeof(treeNum));
for(int i = 0 ; i < n ; i++){
scanf("%d%d" , &x , &y);
add(y , x , 1);
}
scanf("%d%d" , &x , &y);
printf("%d\n" , solve(y , x));
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1747400
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告