洛谷P4147 玉蟾宫

P4147 玉蟾宫#

一道难题

题目背景#

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

题目描述#

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

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

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

输入输出格式#

输入格式：

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

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

输出格式：

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

输入输出样例#

输入样例 #1：

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

输出样例 #1：

说明#

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

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

思路#

用一个二维的s数组储存第i行j列的F的上面包括自己有多少个F

然后遍历每一格，往左右延伸，找到最大值。

#include<cstdio>
#include<iostream>
using namespace std;
int n,m;

const int MAXN=1000+5;

int s[MAXN][MAXN];

inline void read(int &x){
    x=0;
    register short k=1;
    register char t=getchar();
    while(t>'9'||t<'0'){
        if(t=='-')k=-k;
        t=getchar();
    }
    while(t>='0'&&t<='9'){
        x*=10;
        x+=(t-'0');
        t=getchar();
    }
    x*=k;
}

int main(){
    read(n);
    read(m);
    char tmp;
    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=m;++j){
            tmp=getchar();
            while(tmp!='F'&&tmp!='R')tmp=getchar();
            if(tmp=='F'){
                s[i][j]=s[i-1][j]+1;
            }
        }
    }
    int ans=0;
    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=m;++j){
            register int l=j,r=j;
            while(l>=1&&s[i][l]>=s[i][j])--l;
            while(r<=m&&s[i][r]>=s[i][j])++r;
            ++l;
            --r;
            ans=max(ans,3*(s[i][j]*(r-l+1)));
        }
    }
    printf("%d\n",ans);
    return 0;
}

然而会超时。不优化超两个点。

快读 + register：超一个点。

使用单调栈（递增）：

参考洛谷这位大佬的题解。

枚举每一行，

然后从左到右（或者从右到左）依次入栈。

栈里存结构体

struct node
{
    int kuan,gao;
} 
//kuan表示竖着那一条可以向左右延展的长度（宽）
//gao表示那一个的往上冲的高

然后每次入栈的元素的宽设为它弹出的元素的宽度和 + 1。

因为弹出的都冲得比他高（或者同样高）

用 tmp 变量记录弹出的宽度总和

每弹一次，求弹掉的高 * tmp，取最大值

全部入过栈之后，全部弹出。重算 tmp 和弹掉的高 * tmp，继续取最大值。

所有行的最大值的最大值 * 3 为答案。。。。。。

完整代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<iostream>
using namespace std;
int n,m;

const int MAXN=1000+5;

int s[MAXN][MAXN]= {{0}};

struct node
{
    int kuan,gao;
} st[MAXN];
int tp,sz;

inline void read(int &x)
{
    x=0;
    register short k=1;
    register char t=getchar();
    while(t>'9'||t<'0')
    {
        if(t=='-')k=-k;
        t=getchar();
    }
    while(t>='0'&&t<='9')
    {
        x*=10;
        x+=(t-'0');
        t=getchar();
    }
    x*=k;
}

int main()
{
    read(n);
    read(m);
    char tmp;
    for(register int i=1; i<=n; ++i)
    {
        for(register int j=1; j<=m; ++j)
        {
            tmp=getchar();
            while(tmp!='F'&&tmp!='R')tmp=getchar();
            if(tmp=='F')
            {
                s[i][j]=s[i-1][j]+1;
            }
        }
    }
    int ans=0;
    for(int i=1; i<=n; ++i)
    {
        int maxs=0;
        st[1].gao=s[i][1];
        st[1].kuan=1;
        tp=1;
        for(int j=2;j<=m;++j){
            int tmp=0;
            while(st[tp].gao>=s[i][j]&&tp){
                tmp+=st[tp].kuan;
                maxs=max(maxs,st[tp].gao*tmp);
                --tp;
            }
            ++tp;
            st[tp].gao=s[i][j];
            st[tp].kuan=tmp+1;
        }
        int tmp=0;
        while(tp){
            tmp+=st[tp].kuan;
            maxs=max(maxs,st[tp].gao*tmp);
            --tp;
        }
        ans=max(ans,maxs);
    }
    printf("%d\n",3*ans);
    return 0;
}