首页 > 代码库 > POJ 2029 Get Many Persimmon Trees（DP）

POJ 2029 Get Many Persimmon Trees（DP）

2024-07-13 09:32:27   220人阅读

题目链接

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

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

 1 //2029 2 #include <stdio.h> 3 #include <string.h> 4 #include <iostream> 5  6 using namespace std ; 7  8 int mapp[110][110] ; 9 10 int main()11 {12     int N ,S,T ,W,H;13     while(scanf("%d",&N) != EOF && N)14     {15         int x,y ;16         memset(mapp,0,sizeof(mapp)) ;17         scanf("%d %d",&W,&H) ;18         for(int i = 0 ; i < N ; i++)19         {20             scanf("%d %d",&x,&y) ;21             mapp[x][y] = 1 ;22         }23         scanf("%d %d",&S,&T) ;24         for(int i = 1 ; i <= W ; i++)25             for(int j = 1 ; j <= H ; j++)26                 mapp[i][j] += (mapp[i-1][j]+mapp[i][j-1]-mapp[i-1][j-1]) ;27         int ans = -1 ;28         for(int i = S ; i <= W ;i ++)29         {30             for(int j = T ; j <= H ; j++)31             {32                 ans = max(ans,mapp[i][j]-mapp[i-S][j]-mapp[i][j-T]+mapp[i-S][j-T]) ;33             }34         }35         printf("%d\n",ans) ;36     }37     return 0 ;38 }
View Code

二维树状数组

 1 #include<iostream> 2 #include<math.h> 3 #include<stdio.h> 4 #include<string.h> 5 #define MAX 102 6 using namespace std; 7 int c[MAX][MAX]; 8 int lowbit(int x) 9 {10     return x & (-x);11 }12 void add( int x,int y)13 {14     int i=x,j=y;15       for(i=x;i<MAX;i+=lowbit(i))16           for(j=y;j<MAX;j+=lowbit(j))17               c[i][j]++;18 }19 int sum(int x,int y)20 {21    int i,k,sum = 0;22     for(i=x; i>0; i-=lowbit(i))23         for(k=y; k>0; k-=lowbit(k))24             sum += c[i][k];25     return sum;26 }27 int main()28 {29     int w,h,i,j,s,t,n;30     int x,y,ans;31     while(scanf("%d",&n))32     {33         if(n==0)break;34         memset(c,0,sizeof(c));35         scanf("%d%d",&w,&h);36         for(i=0;i<n;i++)37         {38             scanf("%d%d",&x,&y);39             add(x,y);40         }41         scanf("%d%d",&s,&t);42         ans=0;43         for(i=s;i<=w;i++)44         {45             for(j=t;j<=h;j++)46             {47                 ans=max(ans,sum(i,j)-sum(i-s,j)-sum(i,j-t)+sum(i-s,j-t));48             }49         }50         printf("%d\n",ans);51     }52 }
View Code


联系
我们