poj 2029 Get Many Persimmon Trees

发布时间:2014-10-23 23:29:58
来源:分享查询网

   本题可以二维树状数组的思想来解决,暴力好像也可以,数据比较小。用二维树状数组,就是枚举指定长宽的矩阵内*号的个数,并求出数目最大的。 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 110; int c[MAXN][MAXN]; int lowbit(int x) { return x & (-x); } void Modefy(int x, int y, int data) { for(int i = x; i < MAXN; i += lowbit(i)) for(int j = y; j < MAXN; j += lowbit(j)) c[i][j] += data; } int GetSum(int x, int y) { int sum = 0; for(int i = x; i >0; i -= lowbit(i)) for(int j = y; j > 0; j -= lowbit(j)) sum += c[i][j]; return sum; } int Querry(int x1, int y1, int x2, int y2) { return GetSum(x2, y2) - GetSum(x1-1,y2) - GetSum(x2, y1-1) + GetSum(x1-1,y1-1); } int main() { int n; int x, y; int w, h; int S, T; while(scanf("%d", &n) != EOF && n) { memset(c, 0, sizeof(c)); scanf("%d %d", &w, &h); for(int i = 1; i <= n; ++i) { scanf("%d %d", &x, &y); Modefy(x, y, 1); } scanf("%d %d", &S, &T); int ans = 0; for(int i = S; i <= w; ++i) for(int j = T; j <= h; ++j) { int sum = Querry(i-S+1, j-T+1, i, j); if(sum > ans) ans = sum; } printf("%d\n", ans); } return 0; }    

返回顶部
查看电脑版