BZOJ-3039: 玉蟾宫

Description

给你一个n*m的矩形，每个位置是字符'F'或'R'，求仅含'F'字符的矩形，使其面积最大，求出这个面积。1<=N,M<=1000

正方形的话可以dp。
预处理出每个点向左最长'F'串的长度，之后枚举矩形最右边的横坐标。发现答案就是该列上子区间长度乘以子区间中每个位置向左最长'F'串长度最小值。那么考虑每个最小值对应区间最大化，单调栈处理每个点上下第一个比其小的点的位置，之后用mi*len更新答案。
想出来了，开心。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int mp[1100][1100],ans,n,m;
int z[1100],L[1100],R[1100];
void work(int *a)
{
    int top=0,j;
    for(j=1;j<=n;++j)
    {
        while(top&&a[j]<=a[z[top]]) top--;
        L[j]=z[top]; z[++top]=j; 
    }
    top=0;
    for(j=n;j;--j)
    {
        while(top&&a[j]<=a[z[top]]) top--;
        R[j]=top?z[top]:n+1; z[++top]=j;
    }
    for(j=1;j<=n;++j) if(a[j]*(R[j]-L[j]-1)>ans) ans=a[j]*(R[j]-L[j]-1);
}
int main()
{
    scanf("%d%d",&n,&m); char sw[10]; int i,j;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
        {
            scanf("%s",sw);
            if(sw[0]=='F') mp[j][i]=mp[j-1][i]+1;
        }
    for(i=1;i<=m;++i) work(mp[i]);
    printf("%d",3*ans);
    return 0;
}