P4147「玉蟾宫」
P4147「玉蟾宫」
hotarugali
发布于 2022-03-01 21:41:53
发布于 2022-03-01 21:41:53
1. 题目
题目链接：P4147「玉蟾宫」 。
题目背景
有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。
题目描述
这片土地被分成N\times M 个格子，每个格子里写着 R 或者 F，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。
现在 freda 要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着 F 并且面积最大。
但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为 S，它们每人给你 S 两银子。
输入格式
第一行两个整数 N，M，表示矩形土地有 N 行 M 列。
接下来 N 行，每行 M 个用空格隔开的字符 F 或 R，描述了矩形土地。
输出格式
输出一个整数，表示你能得到多少银子，即「3×最大 F 矩形土地面积」的值。
输入输出样例
输入 #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输出 #1
45说明/提示
对于 50\% 的数据，1\leq N，M\leq 200。
对于100\% 的数据，1\leq N，M\leq 1000。
2. 题解
分析
典型求最大子矩阵和问题，即求一个 M \times N矩阵中的子矩阵元素和的最大值。这可以用单调栈解决。对于每一行的每一列元素，往上计算连续的 F 的个数，即得到以每一行为基准的一个条形统计图，每个列对应一个条形矩形，矩形的宽为 111 ，高即为该元素往上计算连续的 F 的个数，这就是典型的计算矩形统计图的最大内矩形面积的问题，用 O(N)的单调栈完美解决。由于有 N 行，每一行都构造出一个矩形统计图，故总复杂度为 O(N^2)。
代码
#include <bits/stdc++.h>
#define ll int
#define MAXN 1005
using namespace std;
// 矩形统计图
struct RC {
ll i;
ll v;
RC():i(0), v(0) {}
RC(ll _i, ll _v): i(_i), v(_v) {}
};
// 计算最大子矩阵面积
ll maxRectangle(ll *A, ll n) {
ll ans = 0;
ll depth = 0;
RC stack[MAXN];
stack[depth] = RC(-1,-1);
for(ll i = 0; i < n; ++i) {
RC t(i,A[i]);
ll sdepth = depth;
while(depth && stack[depth].v >= A[i]) {
ans = max(ans, (stack[sdepth].i-stack[depth-1].i)*stack[depth].v);
--depth;
}
stack[++depth] = t;
}
ll sdepth = depth;
while(depth) {
ans = max(ans, (stack[sdepth].i-stack[depth-1].i)*stack[depth].v);
--depth;
}
return ans;
}
int main()
{
ll n, m;
ll a[MAXN][MAXN], b[MAXN][MAXN];
scanf("%d%d", &n, &m);
for(ll i = 0; i < n; ++i) {
for(ll j = 0; j < m; ++j) {
char str[2];
scanf("%s", str);
if(str[0] == 'R') {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}
for(ll j = 0; j < m; ++j) b[0][j] = a[0][j];
for(ll i = 1; i < n; ++i) {
for(ll j = 0; j < m; ++j) {
if(a[i][j]) {
b[i][j] = b[i-1][j] + 1;
} else {
b[i][j] = 0;
}
}
}
ll ans = 0;
for(ll i = 0; i < n; ++i) {
ans = max(ans, maxRectangle(b[i], m));
}
printf("%d\n", 3*ans);
return 0;
}本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录