题目描述

在18世纪，林清司（Seiji Hayashi）长期担任会津藩日新馆武士学校的教授。为表彰他在教育上的功绩，会津藩主松平容颂（Katanobu Matsudaira）决定赐予他一块位于会津盆地大田野中的矩形庄园。庄园的**宽度$W$和高度$H$**由藩主严格指定，但林教授可以自由选择庄园的位置。

田野中种植了许多日本柿子树（会津特产"无籽柿"）。由于林教授特别喜爱柿子，他希望在自己的庄园内尽可能多地包含柿子树。

示例（图1）：

• 整个田野是$10 \times 8$的矩形网格，每个*代表一棵柿子树。
  • 若庄园尺寸为$4 \times 3$（实线区域），最多包含$6$棵树。
  • 若为$6 \times 4$（虚线区域），最多$12$棵。
  • 若为$3 \times 4$（点线区域），最多$5$棵。
• 注意：庄园的宽度和高度不可交换（$4 \times 3$与$3 \times 4$视为不同尺寸）。

输入格式

• 每个测试用例格式如下：

  N
  W H
  x1 y1
  x2 y2
  ...
  xN yN
  S T
  

  • $N$：柿子树数量（$1 \leq N < 500$）。
  • $W, H$：田野的宽度和高度（$1 \leq W, H < 100$）。
  • $x_i, y_i$：第$i$棵树的坐标（原点为$1$，$1 \leq x_i \leq W$，$1 \leq y_i \leq H$，且所有坐标唯一）。
  • $S, T$：庄园的指定宽度和高度（$1 \leq S \leq W$，$1 \leq T \leq H$）。
• 输入以单独一行的$0$结束。

输出格式

对每个测试用例，输出一行：庄园内最多可包含的柿子树数量。

示例

输入：

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

输出：

4
3

解题思路

1. 网格统计：将柿子树位置标记在$W \times H$的二维数组中。
2. 滑动窗口：
   • 计算每个可能的$S \times T$矩形区域内树的数目。
   • 使用前缀和矩阵优化计算，将时间复杂度从$O(N \times W \times H)$降至$O(W \times H)$。
3. 输出最大值：遍历所有可能的矩形位置，统计最大值。

关键公式

• 前缀和矩阵$P$的递推：$$P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + \text{tree}[i][j] $$
• 矩形$(i,j)$到$(i+S-1,j+T-1)$的树数目：$$\text{count} = P[i+S-1][j+T-1] - P[i-1][j+T-1] - P[i+S-1][j-1] + P[i-1][j-1] $$

代码实现（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);  // 将nullptr改为NULL
    
    int cnt;
    while (cin >> cnt && cnt != 0) {
        int W, H;
        cin >> W >> H;
        
        // 使用二维数组标记柿子树的位置
        vector<vector<int> > prefix(W + 1, vector<int>(H + 1, 0));  // 将>>改为> >
        
        // 读入柿子树坐标并构建前缀和数组
        for (int i = 0; i < cnt; ++i) {
            int x, y;
            cin >> x >> y;
            prefix[x][y] = 1;
        }
        
        // 构建二维前缀和数组
        for (int i = 1; i <= W; ++i) {
            for (int j = 1; j <= H; ++j) {
                prefix[i][j] += prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
            }
        }
        
        int S, T;
        cin >> S >> T;
        
        int max_trees = 0;
        
        // 遍历所有可能的矩形
        for (int i = 1; i + S - 1 <= W; ++i) {
            for (int j = 1; j + T - 1 <= H; ++j) {
                int x2 = i + S - 1;
                int y2 = j + T - 1;
                // 利用前缀和数组快速计算矩形内的柿子树数量
                int trees = prefix[x2][y2] - prefix[x2][j - 1] - prefix[i - 1][y2] + prefix[i - 1][j - 1];
                max_trees = max(max_trees, trees);
            }
        }
        
        cout << max_trees << '\n';
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(W \times H)$，适用于$W, H < 100$的约束。
• 空间复杂度：$O(W \times H)$，存储前缀和矩阵。