# 二维树状数组练习 POJ 2029

poj2029题意：
在一块h*w的地上,有n棵柿子树,划t*s的一块矩形地,使得其划到的柿子树最多,输出最多的数量.

16     //有多少棵树
10 8   //地的规模h*w
2 2    //(2,2)处有一棵树
2 5
2 7
3 3
3 8
4 2
4 5
4 8
6 4
6 7
7 5
7 8
8 1
8 4
9 6
10 3
4 3      //划t*s的一块地,这里是t和s
8
6 4
1 2
2 1
2 4
3 4
4 2
5 3
6 1
6 2
3 2
0

```import java.util.Scanner;
public class Main{
static final int N=102;
int C[][];//二维树状数组
int w;
int h ;

private int lowbit(int x ){
return x & ( -x );
}

private void Modify( int x , int y , int c ){
for (int i = x ; i <= w ; i+= lowbit( i ))
for (int j = y ; j <= h ; j+= lowbit( j ))
C[i][j] += c ;
}

private   int Sum (int x , int y ){
int result = 0 ;
for ( int i = x ; i > 0 ; i -= lowbit( i ))
for ( int j = y ; j > 0 ; j -= lowbit( j ))
result += C[i][j] ;
return result ;
}

public static void main(String[] args){
Main ma=new Main();
ma.go();
}

private void go(){
Scanner in=new Scanner(System.in);
int n , x , y;
while(true) {
n=in.nextInt();
if(n==0) break;
w=in.nextInt();
h=in.nextInt();
C=new int[w+1][h+1];
for (int i = 0 ; i < n ; i++ ){
x=in.nextInt();
y=in.nextInt();
Modify(x,y,1 );//将原矩阵(x,y)处的值设置为1,并更新二维树状数组
}
x=in.nextInt();
y=in.nextInt();
int maxx = -1 ;
int sx=0;
for (int  i = x ; i <= w ; i++ )
{
for (int j = y ; j <= h ; j++ )
{
sx = Sum (i,j) + Sum (i-x,j-y)-Sum(i-x,j)-Sum(i,j- y );
if ( sx > maxx )
maxx = sx ;
}
}
System.out.println(maxx);
}
}
}
```

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊

poj 1195 Mobile phones 二维树状数组 Mobile phones Time Limit: 5000MS Memory Limit: 65536K Tot

MatrixTime Limit: 3000MS Memory Limit: 65536K Total Submissions: 9076 Accepted: 3411 Descript
Mobile phones Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 14489 Accepted: 6735
Stars Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/65536 K (Java/Others) Total
1 program hehe; 2 var 3 n,m,i,j,q,x1,y1,x2,y2,co:longint; 4 y:array[0..300,0..300] of longint