B4451 [GESP202512 四级] 建造
前言
这题说是枚举，还要优化
题目来源
B4451 [GESP202512 四级] 建造 - 洛谷
题目描述
小 A 有一张 M 行 N 列的地形图，其中第 i 行第 j 列的数字 aij 代表坐标 (i,j) 的海拔高度。
停机坪为一个 3×3 的区域，且内部所有 9 个点的最大高度和最小高度之差不超过 H。
小 A 想请你计算出，在所有适合建造停机坪的区域中，区域内部 9 个点海拔之和最大是多少。
输入格式
第一行三个正整数 M,N,H，含义如题面所示。
之后 M 行，第 i 行包含 N 个整数 ai1,ai2,…,aiN，代表坐标 (i,j) 的高度。
数据保证总存在一个适合建造停机坪的区域。
输出格式
输出一行，代表最大的海拔之和。
输入输出样例
输入 #1复制
5 5 3 5 5 5 5 5 5 1 5 1 5 5 5 5 5 5 5 2 5 2 5 3 5 5 5 2
输出 #1复制
40
说明/提示
数据范围
对于所有测试点，保证 1≤M,N≤，1≤H,aij≤
。
分析
范围小于1e3，所以时间复杂度应为O()
#include <bits/stdc++.h> using namespace std; const int maxn=1e3+5; int a[maxn][maxn]; int b[maxn][maxn];//3*3范围内最小数 int c[maxn][maxn];//3*3范围内最大数 int d[maxn][maxn];//3*3范围内数之和 int main() { int n,m,h; cin>>n>>m>>h; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { cin>>a[i][j]; b[i][j]=max(b[i][j],a[i][j]); b[i+1][j]=max(b[i+1][j],a[i][j]); b[i+2][j]=max(b[i+2][j],a[i][j]); b[i][j+1]=max(b[i][j+1],a[i][j]); b[i][j+2]=max(b[i][j+2],a[i][j]); b[i+1][j+1]=max(b[i+1][j+1],a[i][j]); b[i+1][j+2]=max(b[i+1][j+2],a[i][j]); b[i+2][j+1]=max(b[i+2][j+1],a[i][j]); b[i+2][j+2]=max(b[i+2][j+2],a[i][j]); if(c[i][j]) c[i][j]=min(c[i][j],a[i][j]); if(!c[i][j]) c[i][j]=a[i][j]; if(c[i+1][j]) c[i+1][j]=min(c[i+1][j],a[i][j]); if(!c[i+1][j]) c[i+1][j]=a[i][j]; if(c[i+2][j]) c[i+2][j]=min(c[i+2][j],a[i][j]); if(!c[i+2][j]) c[i+2][j]=a[i][j]; if(c[i][j+1]) c[i][j+1]=min(c[i][j+1],a[i][j]); if(!c[i][j+1]) c[i][j+1]=a[i][j]; if(c[i][j+2]) c[i][j+2]=min(c[i][j+2],a[i][j]); if(!c[i][j+2]) c[i][j+2]=a[i][j+2]; if(c[i+1][j+1]) c[i+1][j+1]=min(c[i+1][j+1],a[i][j]); if(!c[i+1][j+1]) c[i+1][j+1]=a[i][j]; if(c[i+1][j+2]) c[i+1][j+2]=min(c[i+1][j+2],a[i][j]); if(!c[i+1][j+2]) c[i+1][j+2]=a[i][j]; if(c[i+2][j+1]) c[i+2][j+1]=min(c[i+2][j+1],a[i][j]); if(!c[i+2][j+1]) c[i+2][j+1]=a[i][j]; if(c[i+2][j+2]) c[i+2][j+2]=min(c[i+2][j+2],a[i][j]); if(!c[i+2][j+2]) c[i+2][j+2]=a[i][j]; d[i][j]+=a[i][j]; d[i+1][j]+=a[i][j]; d[i+2][j]+=a[i][j]; d[i][j+1]+=a[i][j]; d[i][j+2]+=a[i][j]; d[i+1][j+1]+=a[i][j]; d[i+1][j+2]+=a[i][j]; d[i+2][j+1]+=a[i][j]; d[i+2][j+2]+=a[i][j]; } } int g=0; for(int i=2; i<n; i++) { for(int j=2; j<m; j++) { if(b[i][j]-c[i][j]<=h) { g=max(g,d[i][j]); } } } cout<<g; return 0; }