学步园

题意：一个由 a, b, c, w, x, y, z 组成的 m 行 n 列(1 ≤ m, n ≤ 1000)的字母矩阵，w 可以转成 a, b，x 可以转成 b, c，y 可以转成 a, c，z 可以转成 a, b, c。问由相同字母组成的最大子矩阵的面积。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2870

——>>依次求a, b, c的最大子矩阵。。

求一个矩阵的最大子矩阵：http://blog.csdn.net/scnu_jiechao/article/details/40677547

#include <cstdio>
#include <cstring>
#include <algorithm>

using std::max;

const int MAXN = 1000 + 10;

int m, n;
int ret;
int h[MAXN];
int L[MAXN], R[MAXN];
char G[MAXN][MAXN];

void Read()
{
    for (int i = 1; i <= m; ++i)
    {
        getchar();
        for (int j = 1; j <= n; ++j)
        {
            G[i][j] = getchar();
        }
    }
}

void Init()
{
    ret = 0;
}

void Dp()
{
    for (int i = 1; i <= n; ++i)
    {
        L[i] = i;
        while (L[i] - 1 >= 1 && h[L[i] - 1] >= h[i])
        {
            L[i] = L[L[i] - 1];
        }
    }
    for (int i = n; i >= 1; --i)
    {
        R[i] = i;
        while (R[i] + 1 <= n && h[R[i] + 1] >= h[i])
        {
            R[i] = R[R[i] + 1];
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        ret = max(ret, (R[i] - L[i] + 1) * h[i]);
    }
}

void GetTargetMax(char target, char c1, char c2, char c3)
{
    memset(h, 0, sizeof(h));
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            char& x = G[i][j];
            if (x == target || x == c1 || x == c2 || x == c3)
            {
                ++h[j];
            }
            else
            {
                h[j] = 0;
            }
        }
        Dp();
    }
}

void Output()
{
    printf("%d\n", ret);
}

int main()
{
    while (scanf("%d%d", &m, &n) == 2)
    {
        Read();
        Init();
        GetTargetMax('a', 'w', 'y', 'z');
        GetTargetMax('b', 'w', 'x', 'z');
        GetTargetMax('c', 'x', 'y', 'z');
        Output();
    }

    return 0;
}

单调栈实现：

#include <cstdio>
#include <cstring>
#include <algorithm>

using std::max;

const int MAXN = 1000 + 10;

int m, n;
int ret;
int h[MAXN];
int L[MAXN], R[MAXN];
char G[MAXN][MAXN];

struct MS
{
    int st[MAXN];
    int top;

    MS(): top(0) {}

    void Init()
    {
        top = 0;
    }

    void PushMin(const int* A, const int& i)
    {
        while (top != 0 && A[i] <= A[st[top - 1]])
        {
            --top;
        }
        st[top++] = i;
    }

    int Size()
    {
        return top;
    }

    int Second()
    {
        return st[top - 2];
    }
};

void Read()
{
    for (int i = 1; i <= m; ++i)
    {
        getchar();
        for (int j = 1; j <= n; ++j)
        {
            G[i][j] = getchar();
        }
    }
}

void Init()
{
    ret = 0;
}

void Update()
{
    MS ms;
    for (int i = 1; i <= n; ++i)
    {
        ms.PushMin(h, i);
        if (ms.Size() == 1)
        {
            L[i] = 1;
        }
        else
        {
            L[i] = ms.Second() + 1;
        }
    }

    ms.Init();
    for (int i = n; i >= 1; --i)
    {
        ms.PushMin(h, i);
        if (ms.Size() == 1)
        {
            R[i] = n;
        }
        else
        {
            R[i] = ms.Second() - 1;
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        ret = max(ret, (R[i] - L[i] + 1) * h[i]);
    }
}

void GetTargetMax(char target, char c1, char c2, char c3)
{
    memset(h, 0, sizeof(h));
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            char& x = G[i][j];
            if (x == target || x == c1 || x == c2 || x == c3)
            {
                ++h[j];
            }
            else
            {
                h[j] = 0;
            }
        }
        Update();
    }
}

void Output()
{
    printf("%d\n", ret);
}

int main()
{
    while (scanf("%d%d", &m, &n) == 2)
    {
        Read();
        Init();
        GetTargetMax('a', 'w', 'y', 'z');
        GetTargetMax('b', 'w', 'x', 'z');
        GetTargetMax('c', 'x', 'y', 'z');
        Output();
    }

    return 0;
}