POJ-2029(二次元ツリー配列)
1664 ワード
http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=13384
n*mの行列をあげます.中には小さい行列があります.もう一つの範囲を与えます.与えられた範囲の中で、最大何本の木がありますか?
考え方:二次元樹状配列……
反省:最初はマトリックスに対して与えられた範囲を直接処理しましたが、結果が間違っていました.
n*mの行列をあげます.中には小さい行列があります.もう一つの範囲を与えます.与えられた範囲の中で、最大何本の木がありますか?
考え方:二次元樹状配列……
反省:最初はマトリックスに対して与えられた範囲を直接処理しましたが、結果が間違っていました.
#include<iostream>
using namespace std;
int s[105][105],c[105][105];
int lowbit(int x)
{
return x&(-x);
}
void updata(int x,int y,int v)
{
int i,j;
for(i=x;i<105;i+=lowbit(i))
{
for(j=y;j<105;j+=lowbit(j))
{
c[i][j]+=v;
}
}
}
int getsum(int x,int y)
{
int i,j,sum=0;
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 t;
while(scanf("%d",&t)>0&&t)
{
memset(c,0,sizeof(c));
memset(s,0,sizeof(s));
int n,m;
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=t;i++)
{
int tmp1,tmp2;
scanf("%d%d",&tmp1,&tmp2);
updata(tmp1,tmp2,1);
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
s[i][j]=getsum(i,j);
int a,b,max=0,k;
scanf("%d%d",&a,&b); // :a,b , -1 , a==3,b==4,
a--; // 3, 4 , -1, 4, 5
b--; // .............
for(i=1;i+a<=n;i++)
for(j=1;j+b<=m;j++)
{
k=s[i+a][j+b]-s[i-1][j+b]-s[i+a][j-1]+s[i-1][j-1];
if(max<k)
max=k;
}
printf("%d
",max);
}
return 0;
}