POJ2029--Get Many Persimmon Trees(枚举+二维树状数组)

暴力枚举起点,然后就是裸的二维树状数组。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>
#include <stack>
#include <vector>
#include <ctype.h>
#define INF 999999999
#define M 105
#define LL long long
#define Min(a,b) a<b?a:b
#define Max(a,b) a>b?a:b
using namespace std;

int c[M][M];
int n,m;

int Lowbit(int x)
{
	return x&(-x);
}

void Update(int x,int y,int d)
{
	int i,j;
	for(i=x;i<=n;i+=Lowbit(i))
	{
		for(j=y;j<=m;j+=Lowbit(j))
			c[i][j]+=d;
	}
}

int Getsum(int x,int y)
{
	int sum=0;
	int i,j;
	for(i=x;i>0;i-=Lowbit(i))
	{
		for(j=y;j>0;j-=Lowbit(j))
		{
			sum+=c[i][j];
		}
	}
	return sum;
}

int main()
{
	int k,x,y,i,j;
	while(scanf("%d",&k),k)
	{
		scanf("%d%d",&n,&m);
		memset(c,0,sizeof(c));
		while(k--)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			Update(a,b,1);
		}
		scanf("%d%d",&x,&y);
		int max=-INF;
		int ans=0;
		for(i=x;i<=n;i++)
		{
			for(j=y;j<=m;j++)
			{
				ans=Getsum(i,j)-Getsum(i,j-y)-Getsum(i-x,j)+Getsum(i-x,j-y);
				if(ans>max)
					max=ans;
			}
		}
		printf("%d\n",max);
	}
	return 0;
}


POJ2029--Get Many Persimmon Trees(枚举+二维树状数组)

上一篇:在测试类里面获取 spring bean 的方法


下一篇:深入解析:分布式系统的事务处理经典问题及模型(转载分享)