首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。