洛谷 P4147 分析（别看）

科技起源

2026-07-08 19:15:11

发布于：河北

2阅读

0回复

0点赞

原题链接

注：本篇中所有坐标 $(i,j)$ 是一般来说存在二维数组中的位置，而非数学上的平面直角坐标系

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值

1.2 题目背景、允许、禁止与限制

背景：有 $n \times m$ 个格子，不是 $F$ 就是 $R$
允许：求一块全部为 $F$ 的子矩形最大面积是多少
禁止：
限制：

1.3 题目数据范围与猜测

$1 \le n,m \le 1000 \longrightarrow O(nm)$

1.4 一句话概括题意

有一个大长方形，求其中全部都是 $F$ 的最大子矩形有多大

2 题目破题推导

注：以下七种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

因为我们知道，让一个矩形尽可能大，一定是让底边尽可能长。
因此对于每个柱子，找左边第一个比它低的和右边第一个比它低的，这样这段区间里，这根柱子就是最低的，能保证这段区间如果放置一个底边长度为左右间距，高为这根柱子高的矩形一定是合法的。
那么更直观讲，对于每根柱子，只需要找左边第一个比它低的，因为遍历到这根柱子为止，它一定还是最低的
~~这是老师讲的方法~~，它需要实时记录当前长度

我也有一种方法，没有老师的复杂，就是对于每根柱子，找左右第一个比它矮的柱子，然后这个区间长度 $\times$ 这根柱子高度

2.3 分情况考虑

那刚刚一直在说柱子高度，如何求呢？

如果当前在地图中是 $R$ ，不管怎样，柱子高度都是 $0$
否则在地图中 $(i,j)$ 的位置如果是 $F$ ，则高度就是 $(i-1,j)$ 的高度 $+1$

2.4 数学

2.5 以终为始、以始为终

2.6 手动推导

2.7 边界测试

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：左/右第一个比它小的数字 $\longrightarrow$ $\huge{单调栈}$
这里我用的是老师的方法

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
#define int long long  // 把int统一换成long long，防止面积相乘爆int

// 栈内存储的结构体
// height：柱子高度
// length：该柱子向左能连续延伸的宽度
struct node{
	int height,length;
}; 

int n, m;
const int N = 1111;  // 题目数据范围n,m<=1000，开1111足够
int pos[N][N];       // pos[i][j]：第i行第j列位置，向上连续F的柱子高度
int ans = 0;         // 全局记录最大全F矩形面积

signed main(){
	// 输入行数n、列数m
	cin >> n >> m;

	// 预处理高度数组pos
	for (int i = 1;i <= n;i++){
		for (int j = 1;j <= m;j++){
			char x;
			cin >> x;
			if (x == 'F'){
				// 当前是可用土地，柱子高度 = 上一行同列高度 + 1
				pos[i][j] = pos[i - 1][j] + 1;
			} else {
				// 当前是R，柱子断裂，高度清零
				pos[i][j] = 0;
			}
		}
	}

	// 逐行处理，把每一行当作柱状图的地面，求该行最大矩形
	for (int k = 1;k <= n;k++){
		int temp = 0;          // 记录当前这一行柱状图的最大矩形面积
		stack<node> s;         // 单调递增栈，存柱子高度+左延伸宽度

		// 从左到右遍历当前行每一列柱子
		for(int i = 1;i <= m;i++){
			int temp_len = 0;  // 累加被弹出柱子的总宽度，每次新柱子重置为0

			// 栈顶柱子高度 >= 当前柱子，说明当前柱子是栈顶的右边界，弹出结算
			while(!s.empty() && s.top().height >= pos[k][i]){
				temp_len += s.top().length;  // 把弹出柱子的宽度累加进来
				temp = max(temp, s.top().height * temp_len); // 计算矩形面积，更新本行最大值
				s.pop();
			}
			// 新柱子入栈：左边累加宽度 + 自身1格
			s.push({pos[k][i], temp_len + 1});
		}

		// 遍历完所有列，栈内剩余递增柱子没有右边界，右边界是数组末尾，统一结算
		int temp_len = 0;
		while(!s.empty()){
			temp_len += s.top().length;
			temp = max(temp, s.top().height * temp_len);
			s.pop();
		}

		// 更新全局最大矩形面积
		ans = max(ans, temp);
	}

	// 题目要求输出最大面积*3
	cout << ans * 3;
	
	return 0;
}