AcWing152.城市游戏（悬线法/单调栈）

题意：

给定一个矩阵，矩阵中只有R和F两个字母。

找出最大的只包含F子矩阵。

数据范围$:N,M\leq 1000$.

思路：

问题其实就是在一个01矩阵中找最大的全1子矩阵。

可以用两种解法，第一种是悬线法$dp$，第二种是单调栈。

悬线法：

设$lef(i,j)$表示在$(i,j)$位置上向左最多可以拓展的距离。

设$rig(i,j)$表示在$(i,j)$位置上向右最多可以拓展的距离。

同时设置$up(i,j)$表示在$(i,j)$位置上向上最多可以拓展的距离。

剩下的推导看代码，写的挺清楚的。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int lef[maxn][maxn];
int rig[maxn][maxn];
int up[maxn][maxn];
int a[maxn][maxn];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            char c[2]; scanf("%s", &c);
            if(c[0] == 'R') a[i][j] = 0;
            else a[i][j] = 1;
        }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(a[i][j] == 0) 
            {
                lef[i][j] = 0;
                up[i][j] = 0;
            }
            else 
            {
                lef[i][j] = lef[i][j-1]+1;
                up[i][j] = up[i-1][j]+1;
            }

            if(a[i][m-j+1] == 0) rig[i][m-j+1] = 0;
            else rig[i][m-j+1] = rig[i][m-j+2]+1;
        }
    int ans = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
    {
        if(up[i][j] > 1)
        {
            lef[i][j] = min(lef[i][j], lef[i-1][j]);
            rig[i][j] = min(rig[i-1][j], rig[i][j]);
        }
        ans = max(ans, up[i][j]*(lef[i][j]+rig[i][j]-1));
    }
    cout << ans*3 << endl;

    return 0;
}

单调栈：

现在有一个01矩阵。

可以这么处理，假设原矩阵是：
$$ \begin{bmatrix} 1&1&1\\\\ 1&0&1\\\\ 1&1&0 \end{bmatrix}\tag{1} $$
那么处理过后的矩阵就是
$$ \begin{bmatrix} 1&1&1\\\\ 2&0&2\\\\ 3&1&0 \end{bmatrix}\tag{2} $$
其实就是一个向下延生的过程。

其中的数字就是直方图的高度，然后就对每一行执行单调栈求直方图最大矩形面积就行了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int a[maxn][maxn];
int n, m;
int s[maxn], p;
int w[maxn];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            char c[2]; scanf("%s", &c);
            if(c[0] == 'R') a[i][j] = 0;
            else 
            {
                a[i][j] = 1;
                a[i][j] = a[i-1][j]+1;
            }

        }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        p = 0;
        for(int j = 1; j <= m+1; j++)
        {
            if(a[i][j] > s[p])
            {
                s[++p] = a[i][j];
                w[p] = 1;
            }
            else
            {
                int width = 0;
                while(a[i][j] < s[p])
                {
                    width += w[p];
                    ans = max(ans, width*s[p]);
                    p--;
                }
                s[++p] = a[i][j]; w[p] = width+1;
            }
        }
    }
    cout << ans*3 << endl;
    return 0;
}