POJ 2029（Get Many Persimmon Trees）

题目大意：一个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;
}