关于二维树状数组请参看:
http://128kj.iteye.com/blog/1746732
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
很明显的二维树状数组,穷举t*s的所有位置,并记录其划到的树的个数和最大值.
下面是AC代码:
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);
}
}
}
分享到:
相关推荐
在本篇中,我们将深入学习二维树状数组的应用,并通过解决POJ 1195问题来实践这一概念。 POJ 1195题目要求我们计算一个二维矩阵中的子矩阵之和。这正是二维树状数组的优势所在,因为我们可以快速地对矩阵的任意矩形...
3. T080.cpp - 可能是关于数组操作的问题,比如矩阵变换,C++的二维数组或者vector数组能很好地处理这类问题。 4. T064.cpp - 可能涉及到字符串处理,如模式匹配,C++的string类和标准模板库(STL)的算法函数(如...
- **技能提升**:项目涉及的数据结构(如二维数组、树形图、向量等)和算法(如字符串处理、文件读写)对于提高编程技能非常有帮助。 - **创新思维**:在解决具体问题时,鼓励学生思考不同的解决方案,培养创新思维...
- 常见的状态定义方法,如一维数组、二维数组等。 - 背包问题的各种变体:0/1背包、完全背包、多重背包等。 #### 5. 数据结构题 数据结构题考察的是对各种数据结构的理解和应用能力,如堆、树、图等。 - **知识点...
我们可以创建一个二维数组dp,其中dp[i]表示使用前i个基因片段能得到的最短序列长度。状态转移方程可能是dp[i] = min(dp[j] + len(genome_i)),j遍历前i-1个基因片段,如果基因片段i可以无缝连接到片段j的末尾。最后...
7.4 树状数组 152 7.5 点树 154 7.6 STL 156 7.7 离散化 157 8.图论 158 8.0 2-SAT 158 8.2 寻找Euler回路 163 8.3 拓扑排序 163 8.4 差分约束系统 164 8.5 笛卡尔树 165 8.6 LCA和RMQ 167 8.7 割和桥 171 8.8 最小...
- **二叉堆、左偏树、二项堆**:高效的树形数据结构。 - **树状数组、线段树**:用于区间查询和更新操作。 - **哈希表、并查集**:灵活的数据结构。 - **动态规划**:解决背包问题、最短路等。 - **记忆化搜索**:...