POJ 2029（Get Many Persimmon Trees）

spoiler posted @ 2011年4月11日 19:29 in 树状数组经典题目 , 1838 阅读

题目大意：一个H * W的大矩形，里面的某些格子种有树。现在要你找出一个h * w的小矩形，使得里面树的数量最多，问最多有多少棵树

题目分析：就是求二维的矩形和，然后枚举各个满足条件矩形和的最大值。

源程序+部分注释：

#include<iostream>
#include<stdio.h>
#include<string.h>
#define lowbit(x) (x&(-x))
using namespace std;
 
int w,h;
int c[120][120];
 
int getsum(int x,int y){
    int i=x,j,sum=0;
    while(i){
        j=y;
        while(j){
            sum+=c[i][j];
            j-=lowbit(j);
        }
        i-=lowbit(i);
    }
    return sum;
}   
 
int modify(int x,int y){
    int k;
    while(x<=w){
        k=y;
        while(k<=h){
            c[x][k]+=1;
            k+=lowbit(k);       
        }
        x+=lowbit(x);
    }
    return 0;
}
 
int count_sum(int x,int y,int xm,int ym){
    int sum=0;
    sum=getsum(x,y)-getsum(x-xm,y)-getsum(x,y-ym)+getsum(x-xm,y-ym);
    return sum;
}
 
int main(){
    int n,s,t;
    int i,j,x,y,max,ans;
    while(scanf("%d",&n),n){
        memset(c,0,sizeof(c));
        max=0;  
        scanf("%d %d",&w,&h);
        for(i=1;i<=n;i++){
            scanf("%d %d",&x,&y);
            modify(x,y);
        }
        scanf("%d %d",&s,&t);
        for(i=s;i<=w;i++)
            for(j=t;j<=h;j++){
                ans=count_sum(i,j,s,t); 
                if(max<ans)
                    max=ans;
            }
        cout<<max<<endl;
    }
    return 0;
}