P4147 玉蟾宫 题解

题目链接

P4147 玉蟾宫

简要思路

很容易发现，这是最大子矩形问题的板子题。

定义一个二维的 \(dp\) 数组，\(dp_{i,j}\) 代表以坐标 \((i,j)\) 为底的线段，最长能向上延伸多少个单位长度的 F（如果自身为 R，值则为 \(0\)）。

对于 \(dp\) 数组的维护，分为两种情况：

1. 当 \(a_{i,j}\) 为 F 时，\(dp_{i,j}=dp_{i-1,j}+1\)；

2. 否则当 \(a_{i,j}\) 为 R 时，\(dp_{i,j}\) 为默认值 \(0\)。

核心做法为单调栈，栈顶为最大值。栈内存储的值的类型为一个结构体，该结构体以列为中心，存储两个内容：当前的点最长向上延伸的 F 的单位长度 \(h\)，和其对应的可控宽度 \(w\)。

具体操作过程如下：

1. 枚举每一行，对每一行进行 solve 操作；

2. 把该行的第一列作为起点压入栈中，进行单调栈操作；

3. 维护一个变量 \(sum\)，用于记录当前单调栈过程中弹出的元素的可控宽度之和；

4. 枚举每一行，判断当前位置与栈顶的关系：

   • 如果当前栈顶 \(\geq\) 当前元素，我们维护当前可控宽度之和加上当前元素的可控宽度，那么此时的面积就是当前元素的高 \(h \times\) 当前之前弹出元素的可控宽度之和 \(sum\)；

   • 否则直接压入栈中即可。

5. 维护当前元素结构体中的信息：长度 \(h\) 为 \(dp\) 数组中相应位置的值，可控宽度 \(w\) 为当前弹出元素的可控宽度之和 \(sum + 1\)（因为要加上自己）；

6. 最后整行枚举完后，我们在遍历栈中剩余的元素，计算其面积并维护答案。

完整代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int MAXN=1005;

int n,m,maxn;
char c[MAXN][MAXN];
int dp[MAXN][MAXN];

struct node{
	int h,w;//长度和宽度
}a[MAXN];//以列为中心
std::stack<node> s;//存储类型为 node

void solve(int x){
	memset(a,0,sizeof(a));
	while(s.size())s.pop();//先清空
	
	a[1].h=dp[x][1],a[1].w=1;
	s.push(a[1]);//处理好每行的第一列元素
	
	for(int i=2;i<=m;i++){
		int sum=0;//当前可控宽度之和
		while(s.size()&&s.top().h>=dp[x][i]){//需要先弹出再压入
			sum+=s.top().w;//更新当前可控宽度之和
			maxn=std::max(maxn,s.top().h*sum);//计算当前面积
			s.pop();
		}
		a[i].h=dp[x][i],a[i].w=sum+1;//可控宽度加上自己
		s.push(a[i]);
	}
	
	int sum=0;
	while(s.size()){//处理栈中剩余的元素/矩形
		sum+=s.top().w;
		maxn=std::max(maxn,s.top().h*sum);
		s.pop();
	}
}

signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	std::cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			std::cin>>c[i][j];
			if(c[i][j]=='F')dp[i][j]=dp[i-1][j]+1;//dp 数组的维护，为 R 则为默认值 0
		}

	for(int i=1;i<=n;i++)solve(i);//对于每一行解决子问题
	std::cout<<maxn*3<<endl;//注意 *3
	return 0;
}