[BZOJ 3039&洛谷P4147]玉蟾宫 题解（单调栈）

时间：2021-07-15 02:36:47

[BZOJ 3039&洛谷P4147]玉蟾宫

Description

有一天，小猫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'，描述了矩形土地。

输出格式：

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

Solution

1.我们按行去划分，O(n)枚举行，对该行即以上的部分做最大矩阵处理；

2.那么我们用pos数组记录每行向上可延伸的最大距离，预处理的方式即为：

(1)读到一个‘F’，该处pos=上一行该列pos的值+1；

(2)读到一个‘R’，该处pos=0（因为该处不可向上伸展）；

memset(pos,0,sizeof(pos));

for(i=1;i<=n;++i)

	for(j=1;j<=m;++j){

		x=getc();

		if(x=='F')pos[i][j]=pos[i-1][j]+1;

	}

3.那么对于每次枚举的行即期以上部分:从左往右或从右往左进行一次单增栈，每次弹栈时更新最大面积;

(1)栈内每个单位存入两个元素：该单位高度height和对应可控宽度length，对于每个大于栈顶直接入栈的元素，stack[i].length=1；

(2)对于需要先弹栈再入栈的元素，其length=弹栈所有元素length之和+1，因为被弹栈的元素的高度均≥当前元素，所以其可控范围应加上被其弹栈元素的length；

(3)在弹栈过程中，记录一个temp为本次弹栈到当前为止弹出的宽度，因为为单增栈，所以每个高度均可控其后被弹栈元素的宽度，所以其对应的面积为s=temp*h[i]，取max更新该行的maxs；

4.对每次枚举的maxs取max即为最终答案；

Code

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

struct node{

	int height,length;

}stack[1010];

int n,m,i,j,k,pos[1010][1010],ans=0,maxs=0;

char x;

inline int read(){

	int x=0;

	bool f=true;

	char c;

	c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') f=false;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		x=(x<<1)+(x<<3)+(c^48);

		c=getchar();

	}

	return f?x:-x;

} 

char getc()

{

	char c=getchar();

	while(c!='R'&&c!='F')c=getchar();

	return c;

}

void calc(int x){

	int top=1,temp=0;

	maxs=0;

	stack[1].height=pos[x][1];

	stack[1].length=1;

	for(i=2;i<=m;++i){

		temp=0;

		while(stack[top].height>=pos[x][i]&&top>0){

			temp+=stack[top].length;

			maxs=max(maxs,stack[top--].height*temp);

		}

		stack[++top].height=pos[x][i];

		stack[top].length=temp+1;

	}

	temp=0;

	while(top>0){

		temp+=stack[top].length;

		maxs=max(maxs,stack[top--].height*temp);

	}

	ans=max(ans,maxs);

}

int main(){

	memset(pos,0,sizeof(pos));

	n=read();

	m=read();

	for(i=1;i<=n;++i)

		for(j=1;j<=m;++j){

			x=getc();

			if(x=='F')pos[i][j]=pos[i-1][j]+1;

		}

	for(k=1;k<=n;++k) calc(k);

	ans*=3;

	printf("%lld\n",ans);

	return 0;

}

单调栈基础知识部分可以参考我的题解：http://www.cnblogs.com/COLIN-LIGHTNING/p/8474668.html

相关文章