Luogu P4147 Jade Toad Palace

P4147 Jade Toad Palace#

A difficult problem

Problem Background#

One day, the little cat Rainbow and Freda came to the Jade Toad Palace on Tianmen Mountain in Zhangjiajie, Xiangxi. The palace owner, Blue Rabbit, warmly welcomed them and gave them a piece of land.

Problem Description#

This piece of land is divided into N*M grids, with each grid marked with 'R' or 'F', where 'R' represents the land given to Rainbow and 'F' represents the land given to Freda.

Now Freda wants to be cute here... She wants to find a rectangular piece of land that is all marked with 'F' and has the maximum area.

But Rainbow and Freda are not good at competitive programming, so they can't find this piece of land. Blue Rabbit also wants to see Freda being cute (obviously, she can't code...), so they decided that if you find a piece of land with an area of S, they will give you S silver coins each.

Input/Output Format#

Input Format:

The first line contains two integers N and M, indicating the land has N rows and M columns.

The next N lines contain M characters separated by spaces, describing the rectangular land.

Output Format:

Output an integer, indicating how many silver coins you can get, which is the value of (3 * the area of the largest 'F' rectangular land).

Input/Output Example#

Input Example #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

Output Example #1:

Explanation#

For 50% of the data, 1 <= N, M <= 200

For 100% of the data, 1 <= N, M <= 1000

Approach#

Use a two-dimensional array s to store the number of 'F's above and including the 'F' in the i-th row and j-th column.

Then iterate through each grid and extend to the left and right to find the maximum value.

#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;
}

However, it will exceed the time limit. Optimize it to pass two more test cases.

Use fast input and register: Pass one more test case.

Use a monotonic stack (increasing):

Refer to the solution of this great person.

Enumerate each row,

Then push from left to right (or right to left) one by one.

The stack stores a structure

struct node
{
    int width, height;
} 
// width represents the length (width) that can be extended to the left and right vertically
// height represents the height that goes up

Then set the width of each element pushed into the stack as the sum of the widths of the elements popped out plus 1.

Because the popped elements are higher (or the same height)

Use a tmp variable to record the sum of the popped widths

For each pop, calculate the height * tmp and take the maximum value

After all elements have been pushed into the stack, pop them all. Recalculate tmp and the height * tmp, continue to take the maximum value.

The maximum value of the maximum value of all rows * 3 is the answer...

Complete code

#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 width, height;
} 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].height=s[i][1];
        st[1].width=1;
        tp=1;
        for(int j=2;j<=m;++j){
            int tmp=0;
            while(st[tp].height>=s[i][j]&&tp){
                tmp+=st[tp].width;
                maxs=max(maxs,st[tp].height*tmp);
                --tp;
            }
            ++tp;
            st[tp].height=s[i][j];
            st[tp].width=tmp+1;
        }
        int tmp=0;
        while(tp){
            tmp+=st[tp].width;
            maxs=max(maxs,st[tp].height*tmp);
            --tp;
        }
        ans=max(ans,maxs);
    }
    printf("%d\n",3*ans);
    return 0;
}