1. 题目

题目链接：P4147「玉蟾宫」 。

题目背景

有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。

题目描述

这片土地被分成 $N\times M$ 个格子，每个格子里写着 R 或者 F，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。

现在 freda 要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着 F 并且面积最大。

但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为 $S$，它们每人给你 $S$ 两银子。

输入格式

第一行两个整数 $N$，$M$，表示矩形土地有 NN 行 $M$ 列。

接下来 $N$ 行，每行 $M$ 个用空格隔开的字符 F 或 R，描述了矩形土地。

输出格式

输出一个整数，表示你能得到多少银子，即「$3\times$最大 F 矩形土地面积」的值。

输入输出样例

输入 #1

5 6 
R F F F F F 
F F F F F F 
R R R F F F 
F F F F F F 
F F F F F F

输出 #1

45

说明/提示

对于 $50\%$ 的数据，$1\leq N$，$M\leq 200$ 。

对于 $100\%$ 的数据，$1\leq N$，$M\leq 1000$ 。

2. 题解

分析

典型求最大子矩阵和问题，即求一个 $M \times N$ 矩阵中的子矩阵元素和的最大值。这可以用单调栈解决。对于每一行的每一列元素，往上计算连续的 F 的个数，即得到以每一行为基准的一个条形统计图，每个列对应一个条形矩形，矩形的宽为 $1$ ，高即为该元素往上计算连续的 F 的个数，这就是典型的计算矩形统计图的最大内矩形面积的问题，用 $O(N)$ 的单调栈完美解决。由于有 $N$ 行，每一行都构造出一个矩形统计图，故总复杂度为 $O(N^2)$ 。

代码

#include <bits/stdc++.h>
#define ll int
#define MAXN 1005
using namespace std;

// 矩形统计图
struct RC {
    ll i;
    ll v;
    RC():i(0), v(0) {}
    RC(ll _i, ll _v): i(_i), v(_v) {}
};


// 计算最大子矩阵面积
ll maxRectangle(ll *A, ll n) {
    ll ans = 0;
    ll depth = 0;
    RC stack[MAXN];
    stack[depth] = RC(-1,-1);
    for(ll i = 0; i < n; ++i) {
        RC t(i,A[i]);
        ll sdepth = depth;
        while(depth && stack[depth].v >= A[i]) {
            ans = max(ans, (stack[sdepth].i-stack[depth-1].i)*stack[depth].v);
            --depth;  
        }
        stack[++depth] = t;
    }
    ll sdepth = depth;
    while(depth) {
        ans = max(ans, (stack[sdepth].i-stack[depth-1].i)*stack[depth].v);
        --depth; 
    }
    return ans;
}

int main()
{
    ll n, m;
    ll a[MAXN][MAXN], b[MAXN][MAXN];
    scanf("%d%d", &n, &m);
    for(ll i = 0; i < n; ++i) {
        for(ll j = 0; j < m; ++j) {
            char str[2];
            scanf("%s", str);
            if(str[0] == 'R') {
                a[i][j] = 0;
            } else {
                a[i][j] = 1;
            }
        }
    }
    for(ll j = 0; j < m; ++j)  b[0][j] = a[0][j];
    for(ll i = 1; i < n; ++i) {
        for(ll j = 0; j < m; ++j) {
            if(a[i][j]) {
                b[i][j] = b[i-1][j] + 1;
            } else {
                b[i][j] = 0;
            }
        }
    }
    ll ans = 0;
    for(ll i = 0; i < n; ++i) {
        ans = max(ans, maxRectangle(b[i], m));
    }
    printf("%d\n", 3*ans);
    return 0;
}