题目描述

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

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

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

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

输入格式

第一行包括两个整数N,M，表示矩形土地有N行M列。

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

每行末尾没有多余空格。

输出格式

输出一个整数，表示你能得到多少银子，即(3*最大’F’矩形土地面积)的值。

数据范围

1≤N,M≤1000

样例

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

45

算法1:DP....吧

dp[i][j]表示点(i,j)往上的高度,比如样例中的 dp[2][3] = 2 dp[4][4] = 4
然后从j到左遍历遇到是F的点 就更新最小的高度 代码很少 应该很容易看懂

时间复杂度:O(NMM)

C++ 代码

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
char citymap[1001][1001]{ 0 };
int dp[1001][1001]{ 0 };
int main(int argc, char const* argv[])
{
    int maxret = 0;
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> citymap[i][j];
            if (citymap[i][j] == 'F') {
                int height = 0;
                dp[i][j] = dp[i - 1][j] + 1;
                height = dp[i][j];
                for (int x = j; x >= 1 && citymap[i][x] == 'F'; x--) {
                    height = min(dp[i][x], height);
                    maxret = max(maxret, height * (j + 1 - x));
                }
            }
        }
    }
    cout << maxret*3;
    return 0;
}