申请会员ID：Quick_Sort【申请通过】

发表于 2024-2-7 12:37

1、申请 ID：Quick_Sort
2、个人邮箱：2673107978@qq.com
3、原创技术文章：

洛谷 P4147 玉蟾宫题解

题目背景 & 描述

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

输出格式

输出一个整数，表示你能得到多少银子，即（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

对于 100% 的数据，1 ≤ N, M ≤ 1000。

题目分析

画个图分析分析

https://imgse.com/i/pF1p1AS

肉眼可见这一块面积最大

https://imgse.com/i/pF1pJpj

可是我们要如何用编程来求出呢？

以下将 F 设为 “土地” ，将 R 称为 "障碍"

可以想象一下，每一块土地，有一条线，从土地本身一直向上延伸，直到遇到了边界或者障碍，我们把这条线的长度叫 h

我们给每一个土地都计算出它的 h

https://imgse.com/i/pF1pODP

然后，我们要计算每一条线可以往左和右最远可以到达的地方，之后，就可以遍历计算面积并获得最大值了。

那，我们要如何计算每一条线可以往左和右最远可以到达的地方呢？

以下如果不理解，就多看几遍

我们先计算每一个土地可以从自身向左和右可以到达最远的地方，我们叫它 l 和 r 。

https://imgse.com/i/pF193b6

接下来，计算每一条线可以往左和右最远可以到达的地方。当这个土地的上面也是一个土地时，如果上面土地的 r 小于下面的土地，那么下面的土地的 r 更新为上面土地的 r ，如果上面土地的 l 大于下面的土地的 l ，则下面的 l 更新为上面的 l。

可以思考一下，为什么这样做。

更新后的图如下：

https://imgse.com/i/pF1tGe1

加上前面的关于 h 的图

https://imgse.com/i/pF1pODP

我们就可以很轻松的获得每条线所可以覆盖的土地面积了

用公式 (r - l + 1) * h 就可以计算

最后，当全部计算结束，比较大小就可以获得最大的空地面积了

这就是竞赛中常用来解决最大子矩形问题的算法：悬线算法

思路有了，代码开写！

代码开写

1. 读入

过简单，不介绍

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
   cin >> a;
   // 初始化 h
   h = 1;
}

然后计算每个土地的 h

// 要计算其他的 h ，如果这个是土地且上面也是土地，则这个土地的 h 等于上面土地的 h 加一
for (int i = 2; i <= n; i++)
for (int j = 1; j <= m; j++)
   if (a == 'F' && a == 'F')
         h = h + 1;

计算 r 和 l

// 计算 r 和 l
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
   // 初始化为 j
   r = j; l = j;
}
// 遍历更新
for (int j = 2, k = m - 1; j <= m; j++, k--) {
   if (a == 'F' && a == 'F')
         // 对于每一行，如果左边的格子是土地，那么更新为左边格子的 l 加一
         l = l;
   if (a == 'F' && a == 'F')
         // 对于每一行，如果右边的格子是土地，那么更新为左边格子的 l 加一
         r = r;
}
}

for (int i = 2; i <= n; i++)
for (int j = 1; j <= m; j++) {
   if (a == 'F' && a == 'F') {
         // 计算每一条线可以往左和右最远可以到达的地方。
         // 当这个土地的上面也是一个土地时，如果上面土地的 r 小于下面的土地，那么下面的土地的 r 更新为上面土地的 r
         // 如果上面土地的 l 大于下面的土地的 l ，则下面的 l 更新为上面的 l。
         if (r < r) r = r;
         if (l > l) l = l;
   }
}

查找最大的面积

// 遍历每一条悬线的面积
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= m; j++) {
   if (a == 'F' && (r - l + 1) * h > ans) {
         // 更新最大
         ans = (r - l + 1) * h;
   }
}
}

完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;
int n, m, ans, h, l, r;
char a;

int main() {
ans = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++)
   for (int j = 1; j <= m; j++) {
         cin >> a;
         // 初始化 h
         h = 1;
   }

// 要计算其他的 h ，如果这个是土地且上面也是土地，则这个土地的 h 等于上面土地的 h 加一
for (int i = 2; i <= n; i++)
   for (int j = 1; j <= m; j++)
         if (a == 'F' && a == 'F')
            h = h + 1;

// 计算 r 和 l
for (int i = 1; i <= n; i++) {
   for (int j = 1; j <= m; j++) {
         // 初始化为 j
         r = j; l = j;
   }
   // 遍历更新
   for (int j = 2, k = m - 1; j <= m; j++, k--) {
         if (a == 'F' && a == 'F')
            // 对于每一行，如果左边的格子是土地，那么更新为左边格子的 l 加一
            l = l;
         if (a == 'F' && a == 'F')
            // 对于每一行，如果右边的格子是土地，那么更新为左边格子的 l 加一
            r = r;
   }
}

for (int i = 2; i <= n; i++)
   for (int j = 1; j <= m; j++) {
         if (a == 'F' && a == 'F') {
            // 计算每一条线可以往左和右最远可以到达的地方。
            // 当这个土地的上面也是一个土地时，如果上面土地的 r 小于下面的土地，那么下面的土地的 r 更新为上面土地的 r
            // 如果上面土地的 l 大于下面的土地的 l ，则下面的 l 更新为上面的 l。
            if (r < r) r = r;
            if (l > l) l = l;
         }
   }

// 遍历每一条悬线的面积
for (int i = 2; i <= n; i++) {
   for (int j = 1; j <= m; j++) {
         if (a == 'F' && (r - l + 1) * h > ans) {
            // 更新最大
            ans = (r - l + 1) * h;
         }
   }
}

// 输出答案
cout << ans * 3 << endl;

return 0;
}

Hmily 发表于 2024-2-7 16:37

图都挂了看不到，这个题目好像网上很多，文章是原创的吗？

就在今天 发表于 2024-2-7 20:20

这是什么，怎么没有图片，图片哪去了

发表于 2024-2-7 20:58

Hmily 发表于 2024-2-7 16:37
图都挂了看不到，这个题目好像网上很多，文章是原创的吗？

图片不知道为什么挂了，就放上图片的链接吧

https://imgse.com/i/pF1p1AS
https://imgse.com/i/pF1pJpj
https://imgse.com/i/pF1pODP
https://imgse.com/i/pF193b6
https://imgse.com/i/pF1tGe1
https://imgse.com/i/pF1pODP

学过了悬线算法之后，刷题时写的题解，代码和文案原创的

发表于 2024-2-8 10:08

Hmily 发表于 2024-2-7 16:37
图都挂了看不到，这个题目好像网上很多，文章是原创的吗？

是原创的

发表于 2024-2-9 10:20

Hmily 发表于 2024-2-7 16:37
图都挂了看不到，这个题目好像网上很多，文章是原创的吗？

不知为什么挂了
https://imgse.com/i/pF1p1AS

https://imgse.com/i/pF1pJpj

https://imgse.com/i/pF1pODP

https://imgse.com/i/pF193b6

https://imgse.com/i/pF1tGe1

https://imgse.com/i/pF1pODP

都是原创

发表于 2024-2-9 10:25

Hmily 发表于 2024-2-7 16:37
图都挂了看不到，这个题目好像网上很多，文章是原创的吗？

图片源文件地址

https://s11.ax1x.com/2024/02/05/pF1p1AS.png
https://s11.ax1x.com/2024/02/05/pF1pJpj.png
https://s11.ax1x.com/2024/02/05/pF1pODP.png
https://s11.ax1x.com/2024/02/05/pF193b6.png
https://s11.ax1x.com/2024/02/06/pF1tGe1.png
https://s11.ax1x.com/2024/02/05/pF1pODP.png

Hmily 发表于 2024-2-10 12:32

I D：Quick_Sort
邮箱：2673107978@qq.com

申请通过，欢迎光临吾爱破解论坛，期待吾爱破解有你更加精彩，ID和密码自己通过邮件密码找回功能修改，请即时登陆并修改密码！
登陆后请在一周内在此帖报道，否则将删除ID信息。

ps：登录后把文章整理一下发到脱壳破解区，期待以后有更多分享。

Quick_Sort 发表于 2024-2-10 21:17

新人报道，感谢审核:handshake

Quick_Sort 发表于 2024-2-10 21:50

Hmily 发表于 2024-2-10 12:32
I D：Quick_Sort
邮箱：

已经整理发布~

页: [1]

吾爱破解 - LCG - LSG |安卓破解|病毒分析|www.52pojie.cn's Archiver

申请会员ID：Quick_Sort【申请通过】