2029.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"

int sum[1025][1025],n, m;

inline int lowbit(int a)
{
	return a&(a^(a-1));
}

void init()
{
	int i,j;
	
	scanf("%d %d", &n, &m);
	
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
		sum[i][j]=0;
}

void set()
{
	int x,y,a,j;

	scanf("%d %d",&x,&y);
	

	while(x<=n)
	{
		for(j=y;j<=m;j+=lowbit(j))
		{
			sum[x][j]++;
		}
		x+=lowbit(x);
	}
}

int count(int x,int y)
{
	int ans=0,j;
	
	while(x>0)
	{
		for(j=y;j>0;j-=lowbit(j))
		{
			ans+=sum[x][j];
		}
		x-=lowbit(x);
	}

	return ans;
}


int query(int l, int b, int r, int t)
{

	return count(r,t)-count(r,b-1)-count(l-1,t)+count(l-1,b-1);
}

int main()
{
	int tree, w, h, i, j, ans, temp;
	while( scanf( "%d", &tree ) == 1)
	{
		if( tree == 0 ) break;

		init();

		while( tree-- )
			set();
		scanf( "%d %d", &w, &h );
		
		ans = 0;
		for( i=1; i<=n-w+1; i++ )
		for( j=1; j<=m-h+1; j++ )
		if( ( temp = query( i, j, i+w-1, j+h-1 ) ) > ans )
			ans = temp;

		printf( "%d\n", ans );

	}
	return 0;
}