当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

二维树状数组练习 POJ 2029

发表于: 2012-12-13   作者:128kj   来源:转载   浏览:
摘要: 关于二维树状数组请参看: http://128kj.iteye.com/blog/1746732 poj2029题意:    在一块h*w的地上,有n棵柿子树,划t*s的一块矩形地,使得其划到的柿子树最多,输出最多的数量. 样例: 16     //有多少棵树 10 8   //地的规模h*w 2 2
关于二维树状数组请参看: 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 2029

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
接前文:二维树状数组学习之一:彻底理解 http://128kj.iteye.com/blog/1746732 POJ1195题意:大概题
关于树状数组,参看: http://128kj.iteye.com/blog/1743633 POJ3067题意: 东海岸与西海岸分别有N和M
一个水题。。。结果因为一个加号写成了减号。。。硬是耗费了一个多小时。。。T^T Counting Black Ti
楼教主出的二维树状数组。 给出矩阵左上角和右下角坐标,矩阵里的元素 1变0 ,0 变1,然后给出询问
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
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号