2021hdu多校1 Maximal submatrix(单调栈+简单dp)

**题意：**给你一个数字矩阵，让你找一个子矩阵，使其满足每一列是非递减的，输出最大的子矩阵的面积。

题解：

1. 我们根据每一列进行非递减的dp，得到dp是以当前点为结尾的最大非降子序列。

2. 然后根据我蓝书中一道单调栈的题(传送门)，我们可以将每一行的dp当做矩形的高，矩形的宽为1，直接单调栈即可完成计算

   code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const double PI = acos(-1.0);
const int N = 2e3 + 50;
int dp1[N][N];
int a[N][N];
int n, m;
int s[N], w[N];
int solve()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            dp1[i][j] = 0;
            scanf("%d", &a[i][j]);
        }
    for (int i = 1; i <= n; i++)
        dp1[i][m + 1] = 0;

    for (int j = 1; j <= m; j++)
        for (int i = 1; i <= n; i++)
        {

            if (a[i][j] >= a[i - 1][j])
            {
                dp1[i][j] = dp1[i - 1][j] + 1;
            }
            else
                dp1[i][j] = 1;
        }
    
    int ans = 0;
    int p = 0;
    for (int i = 1; i <= n; i++)
    {
        p = 0;
        for (int j = 1; j <= m + 1; j++)
        {
            if (dp1[i][j] > s[p])
            {
                s[++p] = dp1[i][j];
                w[p] = 1;
            }
            else
            {
                int width = 0;
                while (s[p] > dp1[i][j])
                {
                    width += w[p];
                    ans = max(ans, width * s[p]);
                    p--;
                }
                s[++p] = dp1[i][j], w[p] = width + 1;
            }
        }
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        printf("%d\n", solve());
    }
    return 0;
}