子问题：AcWing 131. 直方图中最大的矩形

相当于枚举每行，对每行求子问题，然后求最优的那个。

初始化：从上到下递推，相当于一个小dp

对每行，设三个数组，枚举每个值，分别找到它左边和右边离它最近的比它小的那个值，然后求面积。

对每行求出的面积取个最大就是最终答案。

易错：

• 最后循环变量是m不是n
• 蛋疼的下标

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>

using namespace std;

const int N = 1010;
int n, m;
int a[N][N];

void get(int h[], int bound[])
{
    stack<int> s;
    for (int i = 1; i <= m; i++)
    {
        while (s.size() && h[s.top()] >= h[i])  s.pop();

        if (s.size())   bound[i] = s.top();
        else    bound[i] = 0;

        s.push(i);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            if (c == 'F')   a[i][j] = a[i - 1][j] + 1;
        }
    int res = 0;

    for (int i = 1; i <= n; i++)
    {
        int h[N], l[N], r[N];
        memcpy(h, a[i], sizeof h);

        get(h, l);
        reverse(h + 1, h + 1 + m);
        get(h, r);

        int ans = -1;
        for (int p = 1, q = m; p <= m; p++, q--)
            ans = max(ans, h[q] * (m + 1 - r[q] - l[p] - 1));   //翻转之后的idx太蛋疼了

        res = max(res, ans);
    }
    cout << res * 3;
    return 0;
}