不理解悬线算法
本帖最后由 Ewan-Ahiouy 于 2023-8-10 21:11 编辑rt
这有个案例：luogu P4147
my code
#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 = 1, r = l = j;
}
for (int j = 2; j <= m; j++) if (a == 'F' && a == 'F') l = l;
for (int j = m - 1; j > 0; j--) if (a == 'F' && a == 'F') r = r;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (i > 1 && a == 'F') {
if (a == 'F') {
h = h + 1;
if (l > l) l = l;
if (r < r) r = r;
}
if ((r - l + 1) * h > ans) ans = (r - l + 1) * h;
}
}
cout << 3 * ans << endl;
return 0;
}
不理解怎么可以这样写{:10_291:}
大佬能帮忙解释一下吗？{:10_254:}
这段代码是用来解决悬线算法问题的。下面我逐行解释一下代码的逻辑：
1. 首先定义了一个二维数组 h 用来记录每个位置的高度，以及三个二维数组 l 、 r 和 a 。
2. 接下来输入了矩阵的行数和列数，并使用两层循环遍历矩阵的每个位置。
3. 在内层循环中，首先输入了矩阵中每个位置的字符，并将 h[ i] 、 r[ i] 和 l[ i] 初始化为 j ，表示当前位置的高度、最右边界和最左边界。
4. 然后使用两个循环判断当前位置和前一个位置是否都为字符 F ，如果是，则将当前位置的最左边界 l[ i] 更新为前一个位置的最左边界 l[ i] 。
5. 同样地，使用一个循环判断当前位置和后一个位置是否都为字符 F ，如果是，则将当前位置的最右边界 r[ i] 更新为后一个位置的最右边界 r[ i] 。
6. 接下来的两层循环用来计算每个位置的面积，并更新最大面积 ans 的值。
7. 在外层循环中，如果当前位置和上一个位置都为字符 F ，则更新当前位置的高度 h[ i] 为上一个位置的高度加一，并更新最左边界 l[ i] 为两者中较大的值，最右边界 r[ i] 为两者中较小的值。
8. 最后输出结果 3 * ans 。
总体来说，这段代码的目的是计算矩阵中由字符 F 组成的最大矩形的面积，并输出结果。具体的实现思路是通过动态规划的方式，先计算每个位置的最左边界和最右边界，再计算每个位置的高度，并更新最大面积。希望能够帮助你理解这段代码。 本帖最后由 陶远航 于 2023-8-9 14:59 编辑
单调栈
先输入数据
处理处每个点往上一共有多少个连续的没有被画过的点
然后每一行f和f要赋值一个超级小的数
为了让区间边界终止与此
然后顺序扫一遍找出每一个点
左边距离他最近的一个比他矮的点
然后倒叙扫一遍找出每一个点
右边距离他最近的一个比他矮的店
中间的就是它能够构成的矩阵
矩阵组成方式是
左边区间的长度（包括中间点） * 右边区间的长度（包括中间点） * 宽（也就是f）
累加起来输出就好了
#include<iostream>
#include<cstdio>
#include<stack>
#define int long long
using namespace std;
const int Max = 1005;
int f;
int a;
int r,l;
signed main()
{
char c;
int n,m;
cin >> n >> m;
for(register int i = 1;i <= n;++ i)
{
for(register int j = 1;j <= m;++ j)
{
cin >> c;
if(c == '*')f = 0;
else
f = f + 1;
}
}
for(int i = 1;i <= n;++ i)
f = f = -0x7fffffff;
int ans = 0;
for(register int i = 1;i <= n;++ i)
{
stack<int>s1,s2;
s1.push(1),s2.push(m);
for(register int ii = 2,jj = m - 1;ii <= m + 1,jj >= 0;jj --,++ ii)
{
while(!s1.empty() && f < f)
{
r = ii;
s1.pop();
}
while(!s2.empty() && f <= f)
{
l = jj;
s2.pop();
}
s1.push(ii);s2.push(jj);
}
for(register int j = 1;j <= m;++ j)
ans += (j - l) * (r - j) * f;
}
cout << ans << endl;
return 0;
} 问题理解：
您想要理解悬线算法，并解释给定的代码（luogu P1950）。您希望得到对代码的逐行解释和算法的解释。
解决方案：
给定的代码实现了悬线算法（它可以用来解决一些矩阵相关的问题），并且似乎是为了解决题目P1950。
下面是对给定代码中每一行的逐行解释：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
int n, m, ans, h, l, r;
char a;
这部分代码包含了头文件引用和全局变量的声明，MAXN表示矩阵的最大大小。
int main() {
ans = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a;
h = 1, r = l = j;
}
for (int j = 2; j <= m; j++)
if (a == 'F' && a == 'F')
l = l;
for (int j = m - 1; j > 0; j--)
if (a == 'F' && a == 'F')
r = r;
}
该部分通过读取输入的矩阵大小以及每个位置上的字符构建了矩阵a。并且初始化了变量h、l和r。
对于每一行，它检查相邻两个字符是否为'F'，如果是，则将l数组中位置j的值更新为l（记录了当前位置往左最远的'F'的位置）。随后，它从右向左遍历矩阵的最后一行，如果相邻两个字符都为'F'，则将r数组中位置j的值更新为r（记录了当前位置往右最远的'F'的位置）。
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i > 1 && a == 'F') {
if (a == 'F') {
h = h + 1;
if (l > l)
l = l;
if (r < r)
r = r;
}
if ((r - l + 1) * h > ans)
ans = (r - l + 1) * h;
}
}
}
这部分是算法的主要部分。它使用动态规划的思想，计算了每个位置（i，j）处悬线（由字符'F'组成）的高度h而且记录了最远左端点和最远右端点分别为l和r。
对于每一个位置（i，j），如果当前位置上的字符是'F'，并且该位置上方的字符也是'F'，则更新高度h、左端点l和右端点r。同时，如果通过当前位置构成的矩形面积大于之前的最大面积ans，则更新ans。
最后，输出3 * ans。
希望这个解释对您有所帮助。如果您还有其他问题，请随时提问。
球一个最佳答案谢谢啦！这对我非常重要！{:10_254:}{:10_254:}{:10_254:}
本帖最后由 学习编程中的Ben 于 2023-8-9 15:18 编辑
问题理解：
您想要了解悬线算法（Skyline Algorithm）的工作原理，并希望对给出的代码进行解释。您想知道如何理解这段代码，并希望得到完整修改后的代码。
解决方案：
悬线算法是一种处理二维数据结构的算法，常用于处理矩形区域的相关问题。该算法从左到右扫描矩形的每一列，记录每一列上最高的高度（高度由矩形的底部边界决定）。在此基础上，可以解决多种与矩形区域相关的问题，例如在给定矩形中找到最大的矩形面积。
现在我将对给出的代码进行解释，并提供修改后的完整代码。
#include <iostream>
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 = 1, r = l = j;
}
// 计算每一行内，连续的F字符所对应的最左边界和最右边界
for (int j = 2; j <= m; j++) {
if (a == 'F' && a == 'F')
l = l;
}
for (int j = m - 1; j > 0; j--) {
if (a == 'F' && a == 'F')
r = r;
}
}
// 使用悬线算法计算矩形区域的最大面积
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i > 1 && a == 'F') {
if (a == 'F') {
h = h + 1;
if (l > l)
l = l;
if (r < r)
r = r;
}
if ((r - l + 1) * h > ans)
ans = (r - l + 1) * h;
}
}
}
cout << 3 * ans << endl;
return 0;
}
这段代码的作用是计算给定矩形区域中，由字符'F'组成的最大矩形面积。代码首先读取输入的矩形区域的大小，并将其表示为一个二维字符数组a。然后，通过两次遍历矩形区域的每一行，计算每个字符为'F'时，向上的连续'F'字符所对应的最左边界和最右边界。
接下来，代码使用悬线算法来计算矩形区域的最大面积。通过遍历每个字符，如果当前字符为'F'且上方的字符也为'F'，则更新该位置的高度h、最左边界l和最右边界r。最后，通过计算每个'F'字符所对应的矩形面积，并更新最大面积ans。
最后，输出结果为最大面积的3倍。
希望以上解释对您有所帮助。如果您还有其他问题，请随时提问。
如果回答对你有帮助，请给我一个最佳答案！{:10_254:}{:10_254:}{:10_254:}
学习编程中的Ben 发表于 2023-8-9 14:59
问题理解：
您想要了解悬线算法（Skyline Algorithm）的工作原理，并希望对给出的代码进行解释。您想知道 ...
出bug了{:10_256:} Ewan-Ahiouy 发表于 2023-8-9 14:59
出bug了
不是，因为有 [ i ]恰好就是编辑器标签 [i] 歌者文明清理员 发表于 2023-8-9 15:00
不是，因为有 [ i ]恰好就是编辑器标签
code标签没有封闭 Ewan-Ahiouy 发表于 2023-8-9 15:02
code标签没有封闭
哦，本来Ben写的是 111，然后修复了脚本bug，现在改成了111 歌者文明清理员 发表于 2023-8-9 15:04
一眼f12{:10_249:} Ewan-Ahiouy 发表于 2023-8-9 15:05
一眼f12
真没有 Ewan-Ahiouy 发表于 2023-8-9 15:05
一眼f12
不看看我的回答吗 Ewan-Ahiouy 发表于 2023-8-9 14:59
出bug了
啊啊啊啊啊啊,早就说不改了 给个最佳答案呗!求你了!!!{:10_254:} @zhangjinxuan 《绿题》 zhangjinxuan 发表于 2023-8-9 21:14
《绿题》
？ Ewan-Ahiouy 发表于 2023-8-9 21:14
？
好难{:10_291:} zhangjinxuan 发表于 2023-8-9 21:15
好难
你告诉我悬线算法是什么就好了{:10_323:}
页:
[1]
2