Description
Input
Output
Sample Input
16 10 8 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 8 6 4 1 2 2 1 2 4 3 4 4 2 5 3 6 1 6 2 3 2 0
Sample Output
4 3
大致题意:国王所在的领地有W*H个点,其中n个点处有树, 现在领地上最多允许圈(当然可以少于)大小为S*T的矩形,问最多可圈中多少棵树?
解题思路:枚举起点,用二维树状数组求解。
枚举起点时要注意从行列从S和T开始,直到W和H为止。
用二维树状数组时,要注意update()每次更新时,c[ ] 加的是1。
AC代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 102; int n, w, h, s, t; int c[maxn][maxn]; int lowbit(int x){ return x&(-x); } void update(int x,int y){ for(int i=x; i<maxn; i+=lowbit(i)) for(int j=y; j<maxn; j+=lowbit(j)) c[i][j] ++; } long long sum(int x, int y){ long long ans = 0; for(int i=x; i>0; i-=lowbit(i)) for(int j=y; j>0; j-=lowbit(j)) ans += c[i][j]; return ans; } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int x, y; while(~scanf("%d", &n) && n){ scanf("%d%d", &w, &h); memset(c,0,sizeof(c)); for(int i=1; i<=n; i++){ scanf("%d%d", &x, &y); update(x, y); } scanf("%d%d", &s, &t); long long ans = 0; for(int i=s; i<=w; i++) //枚举起点 for(int 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("%lld\n", ans); } return 0; }
POJ 2029 Get Many Persimmon Trees (二维树状数组)
原文:http://blog.csdn.net/u013446688/article/details/39755313