题解 P2216 【[HAOI2007]理想的正方形】

· · 题解

楼下几位的单调队列很巧妙，但代码比较复杂，不是很好调，这里介绍一种稍微简单一点的做法。

首先看一下朴素做法：直接O(a*b)枚举矩形，再O(n*n)统计矩形中的最大值和最小值，总时间复杂度O(a*b*n*n)，显然会超时。

其中O(a*b)是理论下限，肯定是没法优化的，所以我们想办法优化O(n*n)的部分，也就是快速求出矩形中的最大值和最小值。

我最开始想的办法是预处理递推出矩形中的最大值和最小值，即：用maxv(i,j,k)表示以点(i,j)为左上角的边长为k的矩形中的最大值，然后用递推公式

maxv(i,j,k)=max{maxv(i,j,k-1), maxv(i+1,j+1,k-1), maxv(i+1,j,k-1), maxv(i,j+1,k-1)}

用O(a*b*n)的时间递推出所有边长为n的矩形中的最大值（最小值），再O(a*b)求最小的差值，总时间复杂度O(a*b*n)。代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int INF = 1000000000;
const int maxm = 1000 + 10;
const int maxn = 100 + 10;

int a, b, n;
int grid[maxm][maxm];
int maxv[maxm][maxm], minv[maxm][maxm];

int main ()
{
//    freopen("in.txt", "r", stdin);
    cin >> a >> b >> n;
    for (int i = 0; i < a; i++)
        for (int j = 0; j < b; j++) {
            scanf("%d", &grid[i][j]);
            maxv[i][j] = minv[i][j] = grid[i][j];
        }

    for (int k = 2; k <= n; k++)
        for (int i = 0; i+1 < a; i++)
            for (int j = 0; j+1 < b; j++) {
                maxv[i][j] = max(grid[i][j], max(maxv[i+1][j+1], max(maxv[i+1][j], maxv[i][j+1])));
                minv[i][j] = min(grid[i][j], min(minv[i+1][j+1], min(minv[i+1][j], minv[i][j+1])));
            }

    int ans = INF;
    for (int i = 0; i <= a-n; i++)
        for (int j = 0; j <= b-n; j++)
            ans = min(ans, maxv[i][j]-minv[i][j]);

    cout << ans;
    fclose(stdin);
    return 0;
}

因为程序的常数很小，我本来以为可以过，但是很可惜只得了50分。

那么也就是说即使用O(n)的时间统计最大值（最小值）也不行，那我们就向O(logn)优化。

再看一下上面的递推公式，我们发现其实这个公式很像RMQ问题的预处理代码。那么这样以来问题就清晰了，这其实就是一道二维RMQ问题：用maxv(i,j,k)表示以点(i,j)为左上角边长为2^k的矩形中的最大值，递推公式为

maxv(i,j,k)=max{maxv(i,j,k), maxv(i+2^(k-1),j+2^(k-1),k-1),maxv(i,j+2^(k-1),k-1), maxv(i+2^(k-1),j,k-1) }

查询边长为n的矩形的最大值也是类似的公式，详见代码。

这样以来，我们就得到了一个复杂度为O(a*b*logn)的算法，因为n只有100，所以logn可以忽略不计。代码如下

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int INF = 1000000000;
const int maxm = 1000 + 100;
const int maxn = 100 + 10;
const int maxlog = 10;

int a, b, n;
int logn;
int grid[maxm][maxm];
int maxv[maxm][maxm], minv[maxm][maxm];

int query (int x, int y){
    int _max = 0, _min = 0;
    _max = max(maxv[x][y], max(maxv[x+n-(1<<logn)][y+n-(1<<logn)], max(maxv[x+n-(1<<logn)][y], maxv[x][y+n-(1<<logn)])));
    _min = min(minv[x][y], min(minv[x+n-(1<<logn)][y+n-(1<<logn)], min(minv[x+n-(1<<logn)][y], minv[x][y+n-(1<<logn)])));
    return _max - _min;
}

int main ()
{
//    freopen("in.txt", "r", stdin);
    cin >> a >> b >> n;
    for (int i = 0; i < a; i++)
        for (int j = 0; j < b; j++) {
            scanf("%d", &grid[i][j]);
            maxv[i][j] = minv[i][j] = grid[i][j];
        }

    for (logn = 0; ((1<<(logn+1)) <= n); logn++);
    for (int k = 0; k < logn; k++)
        for (int i = 0; i+(1<<k) < a; i++)
            for (int j = 0; j+(1<<k) < b; j++) {
                maxv[i][j] = max(maxv[i][j], max(maxv[i+(1<<k)][j+(1<<k)], max(maxv[i+(1<<k)][j], maxv[i][j+(1<<k)])));
                minv[i][j] = min(minv[i][j], min(minv[i+(1<<k)][j+(1<<k)], min(minv[i+(1<<k)][j], minv[i][j+(1<<k)])));
            }

    int ans = INF;
    for (int i = 0; i <= a-n; i++)
        for (int j = 0; j <= b-n; j++)
            ans = min(ans, query(i, j));

    cout << ans;
    fclose(stdin);
    return 0;
}