POJ 2029 - Get Many Persimmon Trees

http://poj.org/problem?id=2029

概要

W * H のグリッドが与えられて，そのうち N 個のマスには柿の木が生えている． S * T の領域に含まれる柿の木の数を最大化する問題．

制約

• 0 < N < 500
• 0 < W, H < 100

解法

a[i][j] = (i,j)の左上の領域にある柿の木の数

というテーブル a を作っておくと，(i,j) を右下にした S * T の領域にある柿の木の数は a[i][j] - a[i-T][j] - a[i][j-S] + a[i-T][j-S] で計算できるので，これを 1 <= i <= H, 1 <= j <= W について計算して最大値をとればいい．

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   while (scanf("%d", &N) != EOF && N != 0) {
 9     int W, H;
10     scanf("%d %d", &W, &H);
11     vector<vector<int> > v(H+1, vector<int>(W+1, 0));
12     for (int i = 0; i < N; i++) {
13       int x, y;
14       scanf("%d %d", &x, &y);
15       ++v[y][x];
16     }
17     int S, T;
18     scanf("%d %d", &S, &T);
19     for (int i = 1; i <= H; i++) {
20       for (int j = 1; j <= W; j++) {
21         v[i][j] += v[i-1][j] + v[i][j-1] - v[i-1][j-1];
22       }
23     }
24 
25     int ans = 0;
26     for (int i = T; i <= H; i++) {
27       for (int j = S; j <= W; j++) {
28         ans = max(ans, v[i][j] - v[i-T][j] - v[i][j-S] + v[i-T][j-S]);
29       }
30     }
31     printf("%d\n", ans);
32   }
33   return 0;
34 }