自动搬运

查看原文

来自洛谷，原作者为

	假假 **

搬运于2025-08-24 21:57:01，当前版本为作者最后更新于2018-02-26 20:07:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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即为最终答案；

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

有什么问题欢迎各位大佬指出