【每日一题】ABC311G - One More Grid Task | 单调栈 | 简单

题目内容

原题链接

给定一个 $n$ 行 $m$ 列的矩阵，问权值最大的子矩阵的权值是多少。

对于一个矩阵，其权值定义为矩阵中的最小值 $minv$ 乘上矩阵中所有元素的和。

数据范围

• $1\le n,m\le 300$
• $1\le a_i\le 300$

题解

对于这类矩阵问题，通常做法都是枚举矩阵的下边界和下边界，这样就可以将矩阵看成一个一维数组问题。

考虑对于一个一维数组，找到其中一个子数组（连续子序列），满足子数组的最小值乘上子数组的元素和最大。

那么问题就非常显然了，考虑数组中每个元素作为子数组的最小值，考虑这个子数组的左右端点，就是考虑其左边和右边第一个小于其的元素即可。这个就是单调栈的经典应用，单调栈在这里是 $O(m)$ 的。

时间复杂度：$O(n^{2}m)$

代码

#include 
using namespace std;

const int N = 310;
int a[N][N];
// 列前缀和
int col[N][N];
int stk[N];
// up ~ down 这个上下界内每个列左边第一个小于该列最小值的列
int L[N], R;
// up ~ down 这个上下界内每个列的元素之和 的前缀和
int pre[N];
// up ~ down 这个上下界内每个列的最小值
int cmin[N];

// up ~ down 内一个列的元素和
int up, down;
int v(int idx) {
    return col[down][idx] - col[up - 1][idx];
}

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
            // 每一行的前缀和
            col[i][j] = col[i - 1][j] + a[i][j];
        }

    long long ans = 0;
    // 枚举子矩阵的上下边界
    for (up = 1; up <= n; ++up) {
        for (int j = 1; j <= m; ++j) cmin[j] = a[up][j];
        for (down = up; down <= n; ++down) {
            // 每一列的最小值
            for (int j = 1; j <= m; ++j) cmin[j] = min(cmin[j], a[down][j]);

            int top = 0;
            for (int j = 1; j <= m; ++j) {
                while (top > 0 && cmin[stk[top]] >= cmin[j]) top -= 1;
                if (top == 0) L[j] = 1;
                else L[j] = stk[top] + 1;
                stk[++top] = j;
                // 每一行的前缀和
                pre[j] = pre[j - 1] + v(j);
            }

            top = 0;
            for (int j = m; j >= 1; --j) {
                while (top > 0 && cmin[stk[top]] > cmin[j]) top -= 1;
                if (top == 0) R = m;
                else R = stk[top] - 1;
                stk[++top] = j;
                ans = max(ans, 1ll * (pre[R] - pre[L[j] - 1]) * cmin[j]);
            }
        }
    }

    cout << ans << "\n";

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66