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;
}