P2491 玉蟾宫

时间限制: 1 s
空间限制: 64000 KB
题目等级 : 大师 Master

题目描述 Description

有一天，小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。
这片土地被分成N*M个格子，每个格子里写着'R'或者'F'，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。
现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着'F'并且面积最大。
但是rainbow和freda的OI水平都弱爆了，找不出这块土地，而蓝兔也想看freda卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为S，它们每人给你S两银子。

输入描述 Input Description

第一行两个整数N,M，表示矩形土地有N行M列。
接下来N行，每行M个用空格隔开的字符'F'或'R'，描述了矩形土地。

输出描述 Output Description

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

样例输入 Sample Input

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

样例输出 Sample Output

45

数据范围及提示 Data Size & Hint

对于50%的数据，1<=N,M<=200
对于100%的数据，1<=N,M<=1000

题解

如果用单纯的暴力搜索，可得其复杂度为O(n^4)，显然是会TLE的，所以我们应用DP来优化
网上有其他神犇用单调栈优化的O(n^{3)做法，而显然我这种蒟蒻是无法参透的，我在这里要讲的是一种线性DP做法，优化后复杂度O(n}2)
首先我们对于每个标记为F的点(i,j)维护两个数组l[i][j]和r[i][j]，l[i][j]表示(i,j)这个点向左扩展最远能到达的点的列坐标-1，r[i][j]维护(i,j)这个点向右扩展最远能到达的点的列坐标+1，若该点被标记为R，则l[i][j]=0，r[i][j]=m+1
在这里我们计算面积的思路是每次算出以(i,j)点所在行为底的最大矩形面积，所以要再维护两个数组L[i][j]和R[i][j]，表示该点所在矩形的底的左右端点的列坐标，h[i][j]维护该矩形高，此时状态转移方程显而易见：
L[i][j]=max(l[i][j]+1,L[i-1][j]);
R[i][j]=min(r[i][j]-1,R[i-1][j]);
h[i][j]=h[i-1][j]+1;
我们在维护一个ans初始值为0，每次算出一个面积值，若大于ans则进行更新，最后直接输出ans*3即可，代码如下

C++代码

/*
    Name:Toad Palace
    Copyright:Ricardo_Y_Li
    Author:Ricardo_Y_Li
    Date: 09/07/17 21:23
    Description:NULL
*/

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

bool map[1010][1010];
int l[1010][1010],r[1010][1010];
int L[1010][1010],R[1010][1010],h[1010][1010];
int n,m,ans=0;

int main(){
    ios::sync_with_stdio(false);
    memset(map,0,sizeof(map));
    memset(h,0,sizeof(h));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            char c;
            cin>>c;
            if(c=='F')
                map[i][j]=1;
        }
    for(int i=1;i<=n;i++){
        int t=0;
        for(int j=1;j<=m;j++){
            if(map[i][j])
                l[i][j]=t;
            else{
                L[i][j]=0;
                t=j;
            }
        }
        t=m+1;
        for(int j=m;j>=1;j--){
            if(map[i][j])
                r[i][j]=t;
            else{
                R[i][j]=m+1;
                t=j;
            }
        }
    }
    for(int i=1;i<=m;i++){
        R[0][i]=m+1;
        L[0][i]=0;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(map[i][j]){
            h[i][j]=h[i-1][j]+1;
            L[i][j]=max(l[i][j]+1,L[i-1][j]);
            R[i][j]=min(r[i][j]-1,R[i-1][j]);
            int s=(R[i][j]-L[i][j]+1)*h[i][j];
            if(ans<s)
                ans=s;
            }
        }
    cout<<ans*3;
    return 0;
}

题解 Code[vs] P2491 玉蟾宫