POJ 2029 Get Many Persimmon Trees（DP||二维树状数组）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接

题意：给你每个柿子树的位置，给你已知长宽的矩形，让这个矩形包含最多的柿子树。输出数目

思路：数据不是很大，暴力一下就行，也可以用二维树状数组来做。

 //

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 using namespace std ;

 int mapp[][] ;

 int main()

 {

     int N ,S,T ,W,H;

     while(scanf("%d",&N) != EOF && N)

     {

         int x,y ;

         memset(mapp,,sizeof(mapp)) ;

         scanf("%d %d",&W,&H) ;

         for(int i =  ; i < N ; i++)

         {

             scanf("%d %d",&x,&y) ;

             mapp[x][y] =  ;

         }

         scanf("%d %d",&S,&T) ;

         for(int i =  ; i <= W ; i++)

             for(int j =  ; j <= H ; j++)

                 mapp[i][j] += (mapp[i-][j]+mapp[i][j-]-mapp[i-][j-]) ;

         int ans = - ;

         for(int i = S ; i <= W ;i ++)

         {

             for(int j = T ; j <= H ; j++)

             {

                 ans = max(ans,mapp[i][j]-mapp[i-S][j]-mapp[i][j-T]+mapp[i-S][j-T]) ;

             }

         }

         printf("%d\n",ans) ;

     }

     return  ;

 }

二维树状数组

 #include<iostream>

 #include<math.h>

 #include<stdio.h>

 #include<string.h>

 #define MAX 102

 using namespace std;

 int c[MAX][MAX];

 int lowbit(int x)

 {

     return x & (-x);

 }

 void add( int x,int y)

 {

     int i=x,j=y;

       for(i=x;i<MAX;i+=lowbit(i))

           for(j=y;j<MAX;j+=lowbit(j))

               c[i][j]++;

 }

 int sum(int x,int y)

 {

    int i,k,sum = ;

     for(i=x; i>; i-=lowbit(i))

         for(k=y; k>; k-=lowbit(k))

             sum += c[i][k];

     return sum;

 }

 int main()

 {

     int w,h,i,j,s,t,n;

     int x,y,ans;

     while(scanf("%d",&n))

     {

         if(n==)break;

         memset(c,,sizeof(c));

         scanf("%d%d",&w,&h);

         for(i=;i<n;i++)

         {

             scanf("%d%d",&x,&y);

             add(x,y);

         }

         scanf("%d%d",&s,&t);

         ans=;

         for(i=s;i<=w;i++)

         {

             for(j=t;j<=h;j++)

             {

                 ans=max(ans,sum(i,j)-sum(i-s,j)-sum(i,j-t)+sum(i-s,j-t));

             }

         }

         printf("%d\n",ans);

     }

 }