P7410 题解

备注：此做法来自nzq巨佬

题意：

FJ 有一个边长为 $n (n \leq 500)$， 共有 $n^2$ 个格子的正方形草地，每一个格子有一个 $1...200$ 的绿度值。对于 FJ 的这个草地，有很多个子矩阵。现在需要你求出子矩阵中所有格子的最小值是 $100$ 的子矩阵的个数。

样例:

输入

3
57 120 87
200 100 150
2 141 135

输出

8

_

思路

我们可以发现答案显然等于最小值小于 $100$ 的矩阵的个数减去最小值小于等于 $100$ 的个数。

如何计算这两个值呢？

我们设函数 query(m) 为最小值小于 $m$ 的子矩阵个数，那么答案就等于 query(100)-query(101) 。

这个函数怎么写呢，我们将所有小于 $m$ 的格子设为 $1$, 将所有大于等于 $m$ 的格子设为 $0$， 我们对于每一行记一个 $sum_{i,j}$。

代码如下:

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(a[i][j]<maxx)b[i][j]=1,sum[i][j]=0;
        else sum[i][j]=sum[i][j-1]+1,b[i][j]=0;
    }
}

其中 $a$ 表示该格子的绿度值， $b_{i,j}=1$ 时表示该格子的绿度值小于 $m$ 等于 $1$ 则表示该格子大于 $m$。

显然，如果 $b_{i,k \ldots j}$ 都为 $1$ 时， $sum_{i,j}=j-k+1$， 如果 $b_{i,j}=0$ 则 $sum_{i,j}=0$。

记录完了 $sum$ 和 $b$ 后，我们枚举每一个格子，我们把这个格子作为一个子矩阵的右下角，为了方便，用 $x$ 表示。那么能与 $x$ 符合的左端点有几个呢？我们发现符合条件的子矩阵需要满足它每一个格子都要大于等于 $m$， 这时候我们统计的 $sum$ 就有用了，我们枚举所有与 $x$ 在同一列且在 $x$ 上方的格子(即行数小于等于 $x$ 的格子)，我们看这些格子在 $sum$ 数组中的最小值。将每个最小值累加起来就是 query(m) 的答案了。

AC代码：

#include<bits/stdc++.h>
#pragma G++ optimize(3)
using namespace std;
#define inf 1000000010
const int maxn=510;
int n,a[maxn][maxn],b[maxn][maxn],sum[maxn][maxn];
long long query(int maxx){
    long long ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]<maxx)b[i][j]=1,sum[i][j]=0;
            else sum[i][j]=sum[i][j-1]+1,b[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(b[i][j])continue;
            long long Min=inf;
            for(int k=i;k>=1;k--){
                Min=min(Min,(long long)sum[k][j]);
                ans+=Min;
            }
        }
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    printf("%lld",query(100)-query(101));
    return 0;
}