G4021 [GESP202512 四级] 建造 题解

知识点：二维数组、局部枚举、最值。

解题思路

枚举每个3×3区域，统计最小值、最大值和总和；若最大值减最小值不超过h，取其总和最大值。

为什么正确

所有合法建造位置都有一个被枚举的左上角，条件筛选和收益计算完全对应题意。

易错点

阈值包含等号；没有合法区域时答案为0；边界必须容纳完整3×3。

复杂度

时间O(nm)，每个窗口固定9格；空间O(nm)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,h;
    cin>>n>>m>>h;
    vector<vector<int>>a(n,vector<int>(m));
    for(auto &row:a)for(int &x:row)cin>>x;
    long long ans=0;
    for(int i=0;i+2<n;i++)for(int j=0;j+2<m;j++) {
        int lo=100001,hi=0,sum=0;
        for(int u=i;u<i+3;u++)for(int v=j;v<j+3;v++) {
            lo=min(lo,a[u][v]);
            hi=max(hi,a[u][v]);
            sum+=a[u][v];
        }
        if(hi-lo<=h)ans=max(ans,(long long)sum);
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。