洛谷P4147 玉蟾宫（动规：最大子矩形问题/悬线法）

题目链接：传送门

题目大意：

　　求由F构成的最大子矩阵的面积。输出面积的三倍。

　　1 ≤ N，M ≤ 1000。

思路：

　　悬线法模板题。

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e3 + ;

int N, M;

char mat[MAX_N][MAX_N];

int lef[MAX_N][MAX_N], rig[MAX_N][MAX_N], up[MAX_N][MAX_N];

void init()

{

    for (int i = ; i <= N; i++) {

        for (int j = ; j <= M; j++)

            if (mat[i][j] == 'F')

                lef[i][j] = lef[i][j-] + ;

            else

                lef[i][j] = ;

        for (int j = M; j >= ; j--)

            if (mat[i][j] == 'F')

                rig[i][j] = rig[i][j+] + ;

            else

                rig[i][j] = ;

    }

}

void dp()

{

    int ans = ;

    for (int i = ; i <= N; i++) {

        for (int j = ; j <= M; j++) {

            if (mat[i][j] == 'F') {

                if (i >  && mat[i-][j] == 'F') {

                    up[i][j] = up[i-][j]+;

                    lef[i][j] = min(lef[i][j], lef[i-][j]);

                    rig[i][j] = min(rig[i][j], rig[i-][j]);

                }

                else

                    up[i][j] = ;

            }

            else

                up[i][j] = ;

            int len = rig[i][j] + lef[i][j] - ;

            int high = up[i][j];

            int a = min(len, high);

            ans = max(ans, a*a);

            ans = max(ans, len*high);

        }

    }

    cout << ans* << endl;

}

int main()

{

    cin >> N >> M;

    for (int i = ; i <= N; i++)

        for (int j = ; j <= M; j++)

            cin >> mat[i][j];

    init();

    dp();

    return ;

}