首页 > 代码库 > POJ 2029

POJ 2029

二维树状数组可解此题

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define lowbit(x) (x)&(-x)using namespace std;int sum[105][105],k,n,m;int W,H;void gp(int x,int y){	int t;	for(;x<=n;x+=lowbit(x))	    for(t=y;t<=m;t+=lowbit(t))	      sum[x][t]+=1;}int gs(int x,int y){  int s=0,t;  for(;x;x-=lowbit(x))    for(t=y;t;t-=lowbit(t))      s+=sum[x][t];  return s;}int gst(int x1,int y1,int x2,int y2){	return gs(x2,y2)-gs(x1-1,y2)-gs(x2,y1-1)+gs(x1-1,y1-1);}int main(){	int s,h; int maxt;	while(scanf("%d",&k),k){		maxt=-1;		memset(sum,0,sizeof(sum));		scanf("%d%d",&n,&m);		for(int i=1;i<=k;i++){			scanf("%d%d",&s,&h);			gp(s,h);		}		scanf("%d%d",&W,&H);		for(int i=1;i<=n;i++){			for(int j=1;j<=m;j++){				maxt=max(maxt,gst(i-W<=0?1:(i-W+1),j-H<=0?1:(j-H+1),i,j));			}		}		printf("%d\n",maxt);	}	return 0;}

  

POJ 2029