关于二维树状数组请参看:
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);
}
}
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1745671
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1744222
NULL 博文链接:https://128kj.iteye.com/blog/1746750
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
NULL 博文链接:https://128kj.iteye.com/blog/1757060
晒代码之二——多重背包(POJ1276)
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1733777
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
NULL 博文链接:https://128kj.iteye.com/blog/1754177
NULL 博文链接:https://128kj.iteye.com/blog/1748635
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
NULL 博文链接:https://128kj.iteye.com/blog/1753387
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码