[BZOJ3039] 玉蟾宫

2014-12-02
竞赛题解 / 动态规划
BZOJ

描述 Description

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

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

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

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

输入格式 InputFormat

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

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

输出格式 OutputFormat

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

样例输入 SampleInput

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

样例输出 SampleOutput

45

BZOJ 3039

求极大子矩阵。h[j]表示到当前行第 j 列有多少个连续的 F，len[j]表示当前行以 h[j]为高度的最大子矩阵的左端点，于是用单调栈可以优化。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
using namespace std;
const int maxn=1005;
int i,j,t,n,m,l,r,k,z,y,x;
int a[maxn][maxn],h[maxn],len[maxn];
stack <int> s;
char ch[1];
int ans;
int main()
{
    scanf("%d%d",&n,&m);
    ans=0;
    for (i=1;i<=n;i++)
    {
        while (!s.empty()) s.pop();
        for (j=1;j<=m;j++)
        {
            len[j]=j;
            scanf("%s",ch);
            if (ch[0]=='R') h[j]=0;
            else h[j]=h[j]+1;
            while (!s.empty() && h[j]<h[s.top()])
            {
                ans=max(ans,(j-len[s.top()])*h[s.top()]);
                len[j]=len[s.top()];
                s.pop();
            }
            s.push(j);
        }
        while (!s.empty())
        {
            ans=max(ans,(m+1-len[s.top()])*h[s.top()]);
            s.pop();
        }
    }
    printf("%d\n",ans*3);
    return 0;
}