P2216 [HAOI2007] 理想的正方形

诗久桜月 · 2024-09-14 08:32:15 · 题解

发现没有人和我用同一个做法，遂发题解。

考虑暴力，首先枚举 n\times n 矩形的位置，发现已经 O(ab) 了，而处理内部是 O(n^2) 的肯定会 TLE。

发现 n\times n 矩形每次就是往右移一位，那么减去矩形左边那一列的贡献，再加上新的这一列的贡献即可。

复杂度 O(abn) 可以通过。

inline void Init(){
    memset(maxn,-0x3f,sizeof(maxn));
    memset(minn, 0x7f,sizeof(minn)); 
    for_(i,1,a-n+1){
        for_(j,1,b){
            for_(k,1,n){
                maxn[i][j] = max(maxn[i][j] ,mapp[i+k-1][j]); // maxn_{i,j} 为以 (i,j) 为起点向右延申 n 格的矩阵内最大值 
                minn[i][j] = min(minn[i][j] ,mapp[i+k-1][j]);
            }
        }
    }
}

inline void solve(){
    for_(i,1,a-n+1){
        for_(j,1,b-n+1){
            int MAX=-inf,MIN=inf;
            for_(k,1,n){
                MAX=max(MAX,maxn[i][j+k-1]);
                MIN=min(MIN,minn[i][j+k-1]);
            }
            ANS=min(ANS,MAX-MIN);
        }
    }
    cout << ANS << endl;
}

inline void In(){
    cin >> a >> b >> n;
    for_(i,1,a){
        for_(j,1,b){
            cin >> mapp[i][j] ;
        }
    }
    Init();
    solve();
}