题目描述

难度分:$2265$

输入$n$，$m(1 \leq n,m \leq 300)$和$n$行$m$列的矩阵$A$，元素范围$[1,300]$。

对于$A$的一个非空子矩阵$R$，定义$f(R)=$子矩阵的元素和$\times$子矩阵的最小值。

输出$f(R)$的最大值。

输入样例$1$

3 3
5 4 3
4 3 2
3 2 1

输出样例$1$

48

输入样例$2$

4 5
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4

输出样例$2$

231

输入样例$3$

6 6
1 300 300 300 300 300
300 1 300 300 300 300
300 300 1 300 300 300
300 300 300 1 300 300
300 300 300 300 1 300
300 300 300 300 300 1

输出样例$3$

810000

算法

前缀和+单调栈

预处理

先预处理出矩阵$rmin_{n \times m \times m}$，和矩阵$s_{n \times m}$。其中$rmin[i][l][r]$表示矩阵$A$的第$i$行中，第$l$列到第$r$列的最小值。比较简单，每行用动态规划即可求得，状态转移方程为

$rmin[i][l][r]=min(rmin[i][l][r-1],A[i][r])$

其中$s[i][j]$表示第$i$行前$j$列元素的和，主要用于求每行任意子数组的和。

枚举+单调栈

接下来枚举矩阵$R$的左边界$l$，以及宽度$w$。固定$l$和$w$之后，遍历所有行，构造两个数组$csum_{1 \times n}$和$cmin_{1 \times n}$。其中$csum[i]$表示矩阵$A$第$i$行，子数组$[l,l+w-1]$的累加和，$cmin[i]$表示矩阵$A$第$i$行，子数组$[l,l+w-1]$的最小值，即$rmin[i][l][l+w-1]$。

有了$cmin$，就可以枚举子矩阵中的最小元素$cmin[i]$。由于矩阵$A$中的所有元素都是正数，要想函数$f(R)$的值最大，在最小值确定的情况下只需要矩阵的累加和最大即可，因此利用单调栈计算出每个$cmin[i]$在行方向上能够保持最小值地位的最大范围。$left[i]$表示$cmin[i]$左边离自己最近的，且比自己小的数的行号；$right[i]$表示$cmin[i]$右边离自己最近的，且比自己小的数的行号。此时，以$cmin[i]$为最小值且$f(R)$最大的矩阵在行上的跨度就是$(left[i],right[i])$，$f(R)=cmin[i] \times \Sigma_{k=left[i]+1}^{right[i]-1}csum[k]$，其中的求和操作可以利用$csum$数组的前缀和数组快速求得。

对于每个左边界$l$以及子矩阵宽度$w$，按照以上的单调栈算法维护所有$f(R)$的最大值即可。

复杂度分析

时间复杂度

预处理：每行的区间最小值$rmin$矩阵，时间复杂度为$O(nm^2)$；每行的前缀和矩阵$s$，时间复杂度为$O(nm)$。

算法：外层循环子矩阵宽度以及子矩阵的左端点，时间复杂度为$O(m^2)$；内层得到每行在列区间$[l,r]$的最小值数组$cmin$和区间和数组$csum$，时间复杂度为$O(n)$；单调栈求$cmin$数组中每个元素$cmin[i]$左右两边最近的更小元素，时间复杂度为$O(n)$；最后计算宽度为$r-l+1$的所有子矩阵$R$中$f(R)$的最大值，时间复杂度为$O(n)$。内层循环是有限几次与数据量无关的$O(n)$流程。

综上，算法整体的时间复杂度为$O(nm^2)$。

空间复杂度

经过以上时间复杂度的分析，空间的瓶颈就在于三维矩阵$rmin$，因此额外空间复杂度为$O(nm^2)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;
typedef long long LL;

const int N = 301;
int a[N][N];
LL s[N][N];
int n, m, rmin[N][N][N];

int main() {
    scanf("%d%d", &n, &m);
    memset(rmin, 0x3f, sizeof rmin);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
        }
        for(int j = 1; j <= m; j++) {
            rmin[i][j][j] = a[i][j];
            for(int k = j + 1; k <= m; k++) {
                rmin[i][j][k] = min(rmin[i][j][k - 1], a[i][k]);
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            s[i][j] = s[i][j - 1] + a[i][j];
        }
    }
    LL ans = 0;
    for(int l = 1; l <= m; l++) {
        for(int w = 1; l + w - 1 <= m; w++) {
            vector<LL> cmin, csum;
            for(int i = 1; i <= n; i++) {
                int r = l + w - 1;
                csum.push_back(s[i][r] - s[i][l - 1]);
                cmin.push_back(rmin[i][l][r]);
            }
            for(int i = 1; i < n; i++) {
                csum[i] += csum[i - 1];
            }
            vector<int> left(n, -1), right(n, n);
            stack<int> stk;
            for(int i = 0; i < n; i++) {
                while(!stk.empty() && cmin[stk.top()] >= cmin[i]) {
                    right[stk.top()] = i;
                    stk.pop();
                }
                if(!stk.empty()) left[i] = stk.top();
                stk.push(i);
            }
            for(int i = 0; i < n; i++) {
                int lb = left[i], ub = right[i];
                ans = max(ans, (csum[ub - 1] - (lb >= 0? csum[lb]: 0))*cmin[i]);
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}