POJ 2029 Get Many Persimmon Trees （模板题）【二维树状数组】

题目大意：

给你一个H*W的矩阵，再告诉你有n个坐标有点，问你一个w*h的小矩阵最多能够包括多少个点。

解题分析：
二维树状数组模板题。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int M =100+10;
 7 int tr[M][M];
 8 int n,W,H,w,h;
 9 int lowbit(int x){return x&(-x);}
10 void add(int x,int y,int val){
11     for(int i = x;i <= H;i += lowbit(i)){
12         for(int j = y;j <= W;j += lowbit(j)){
13             tr[i][j] += val;
14         }
15     }
16 }
17 int sum(int x,int y){
18     int ans = 0;
19     for(int i = x;i > 0;i -= lowbit(i)){
20         for(int j = y;j > 0;j -= lowbit(j)){
21             ans += tr[i][j];
22         }
23     }
24     return ans;
25 }
26 int main(){
27     while(scanf("%d",&n)!=EOF,n){
28         memset(tr,0,sizeof(tr));
29         scanf("%d%d",&H,&W);
30         for(int i=1;i<=n;i++){
31             int x,y;
32             scanf("%d%d",&x,&y);
33             add(x,y,1);
34         }
35         scanf("%d%d",&h,&w);
36         int ans=-1;
37         for(int i=h;i<=H;i++){
38             for(int j=w;j<=W;j++){
39                 int res=sum(i,j)-sum(i-h,j)-sum(i,j-w)+sum(i-h,j-w);   //sum(x,y)代表(1,1)到(x,y)这个矩阵包含多少个点 
40                 ans=max(ans,res);
41             }
42         }
43         printf("%d
",ans);
44     }
45     return 0;
46 }

2018-10-17