不理解悬线算法

Ewan-Ahiouy

rt

这有个案例：luogu P4147

my code

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

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

int main() {
    ans = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            h[i][j] = 1, r[i][j] = l[i][j] = j;
        }
        for (int j = 2; j <= m; j++) if (a[i][j] == 'F' && a[i][j - 1] == 'F') l[i][j] = l[i][j - 1];
        for (int j = m - 1; j > 0; j--) if (a[i][j] == 'F' && a[i][j + 1] == 'F') r[i][j] = r[i][j + 1];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (i > 1 && a[i][j] == 'F') {
                if (a[i - 1][j] == 'F') {
                    h[i][j] = h[i - 1][j] + 1;
                    if (l[i - 1][j] > l[i][j]) l[i][j] = l[i - 1][j];
                    if (r[i - 1][j] < r[i][j]) r[i][j] = r[i - 1][j];
                }
                if ((r[i][j] - l[i][j] + 1) * h[i][j] > ans) ans = (r[i][j] - l[i][j] + 1) * h[i][j];
            }
        }
    cout << 3 * ans << endl;

    return 0;
}

不理解怎么可以这样写

大佬能帮忙解释一下吗？

isdkz

这段代码是用来解决悬线算法问题的。下面我逐行解释一下代码的逻辑：

1. 首先定义了一个二维数组 h 用来记录每个位置的高度，以及三个二维数组 l 、 r 和 a 。
2. 接下来输入了矩阵的行数和列数，并使用两层循环遍历矩阵的每个位置。
3. 在内层循环中，首先输入了矩阵中每个位置的字符，并将 h[ i][j] 、 r[ i][j] 和 l[ i][j] 初始化为 j ，表示当前位置的高度、最右边界和最左边界。
4. 然后使用两个循环判断当前位置和前一个位置是否都为字符 F ，如果是，则将当前位置的最左边界 l[ i][j] 更新为前一个位置的最左边界 l[ i][j-1] 。
5. 同样地，使用一个循环判断当前位置和后一个位置是否都为字符 F ，如果是，则将当前位置的最右边界 r[ i][j] 更新为后一个位置的最右边界 r[ i][j+1] 。
6. 接下来的两层循环用来计算每个位置的面积，并更新最大面积 ans 的值。
7. 在外层循环中，如果当前位置和上一个位置都为字符 F ，则更新当前位置的高度 h[ i][j] 为上一个位置的高度加一，并更新最左边界 l[ i][j] 为两者中较大的值，最右边界 r[ i][j] 为两者中较小的值。
8. 最后输出结果 3 * ans 。

总体来说，这段代码的目的是计算矩阵中由字符 F 组成的最大矩形的面积，并输出结果。具体的实现思路是通过动态规划的方式，先计算每个位置的最左边界和最右边界，再计算每个位置的高度，并更新最大面积。希望能够帮助你理解这段代码。

陶远航

单调栈
先输入数据
处理处每个点往上一共有多少个连续的没有被画过的点
然后每一行f[i][0]和f[i][m + 1]要赋值一个超级小的数
为了让区间边界终止与此

然后顺序扫一遍找出每一个点
左边距离他最近的一个比他矮的点
然后倒叙扫一遍找出每一个点
右边距离他最近的一个比他矮的店
中间的就是它能够构成的矩阵
矩阵组成方式是
左边区间的长度（包括中间点） * 右边区间的长度（包括中间点） * 宽（也就是f[i][j]）
累加起来输出就好了

#include<iostream>
#include<cstdio>
#include<stack>
#define int long long

using namespace std;
const int Max = 1005;
int f[Max][Max];
int a[Max]; 
int r[Max],l[Max];
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[i][j] = 0;
                        else
                        f[i][j] = f[i - 1][j] + 1;
                }
        }
        for(int i = 1;i <= n;++ i)
                f[i][0] = f[i][m + 1] = -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[i][ii] < f[i][s1.top()])
                        {
                                r[s1.top()] = ii;
                                s1.pop();
                        }
                        while(!s2.empty() && f[i][jj] <= f[i][s2.top()])
                        {
                                l[s2.top()] = jj;
                                s2.pop();
                        }
                        s1.push(ii);s2.push(jj);
                }
                for(register int j = 1;j <= m;++ j)
                        ans += (j - l[j]) * (r[j] - j) * f[i][j];
        }
        cout << ans << endl;
        return 0;
}

Mike_python小

问题理解：

您想要理解悬线算法，并解释给定的代码（luogu P1950）。您希望得到对代码的逐行解释和算法的解释。

解决方案：

给定的代码实现了悬线算法（它可以用来解决一些矩阵相关的问题），并且似乎是为了解决题目P1950。

下面是对给定代码中每一行的逐行解释：

#include <bits/stdc++.h>using namespace std;const int MAXN = 1010;int n, m, ans, h[MAXN][MAXN], l[MAXN][MAXN], r[MAXN][MAXN];char a[MAXN][MAXN];

这部分代码包含了头文件引用和全局变量的声明，MAXN表示矩阵的最大大小。

int main() {    ans = 0;    cin >> n >> m;    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= m; j++) {            cin >> a[i][j];            h[i][j] = 1, r[i][j] = l[i][j] = j;        }                for (int j = 2; j <= m; j++)            if (a[i][j] == 'F' && a[i][j - 1] == 'F')                l[i][j] = l[i][j - 1];                        for (int j = m - 1; j > 0; j--)            if (a[i][j] == 'F' && a[i][j + 1] == 'F')                r[i][j] = r[i][j + 1];    }

该部分通过读取输入的矩阵大小以及每个位置上的字符构建了矩阵a。并且初始化了变量h、l和r。

对于每一行，它检查相邻两个字符是否为'F'，如果是，则将l数组中位置j的值更新为l[i][j - 1]（记录了当前位置往左最远的'F'的位置）。随后，它从右向左遍历矩阵的最后一行，如果相邻两个字符都为'F'，则将r数组中位置j的值更新为r[i][j + 1]（记录了当前位置往右最远的'F'的位置）。

    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= m; j++) {            if (i > 1 && a[i][j] == 'F') {                if (a[i - 1][j] == 'F') {                    h[i][j] = h[i - 1][j] + 1;                    if (l[i - 1][j] > l[i][j])                        l[i][j] = l[i - 1][j];                    if (r[i - 1][j] < r[i][j])                        r[i][j] = r[i - 1][j];                }                if ((r[i][j] - l[i][j] + 1) * h[i][j] > ans)                    ans = (r[i][j] - l[i][j] + 1) * h[i][j];            }        }    }

这部分是算法的主要部分。它使用动态规划的思想，计算了每个位置（i，j）处悬线（由字符'F'组成）的高度h[i][j]而且记录了最远左端点和最远右端点分别为l[i][j]和r[i][j]。

对于每一个位置（i，j），如果当前位置上的字符是'F'，并且该位置上方的字符也是'F'，则更新高度h[i][j]、左端点l[i][j]和右端点r[i][j]。同时，如果通过当前位置构成的矩形面积大于之前的最大面积ans，则更新ans。

最后，输出3 * ans。

希望这个解释对您有所帮助。如果您还有其他问题，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！

学习编程中的Ben

问题理解：

您想要了解悬线算法（Skyline Algorithm）的工作原理，并希望对给出的代码进行解释。您想知道如何理解这段代码，并希望得到完整修改后的代码。

解决方案：

悬线算法是一种处理二维数据结构的算法，常用于处理矩形区域的相关问题。该算法从左到右扫描矩形的每一列，记录每一列上最高的高度（高度由矩形的底部边界决定）。在此基础上，可以解决多种与矩形区域相关的问题，例如在给定矩形中找到最大的矩形面积。

现在我将对给出的代码进行解释，并提供修改后的完整代码。

#include <iostream>
using namespace std;

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

int main() {
    ans = 0;
    cin >> n >> m;

    // 读取矩形区域的字符表示
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            h[i][j] = 1, r[i][j] = l[i][j] = j;
        }
        // 计算每一行内，连续的F字符所对应的最左边界和最右边界
        for (int j = 2; j <= m; j++) {
            if (a[i][j] == 'F' && a[i][j - 1] == 'F')
                l[i][j] = l[i][j - 1];
        }
        for (int j = m - 1; j > 0; j--) {
            if (a[i][j] == 'F' && a[i][j + 1] == 'F')
                r[i][j] = r[i][j + 1];
        }
    }

    // 使用悬线算法计算矩形区域的最大面积
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i > 1 && a[i][j] == 'F') {
                if (a[i - 1][j] == 'F') {
                    h[i][j] = h[i - 1][j] + 1;
                    if (l[i - 1][j] > l[i][j])
                        l[i][j] = l[i - 1][j];
                    if (r[i - 1][j] < r[i][j])
                        r[i][j] = r[i - 1][j];
                }
                if ((r[i][j] - l[i][j] + 1) * h[i][j] > ans)
                    ans = (r[i][j] - l[i][j] + 1) * h[i][j];
            }
        }
    }

    cout << 3 * ans << endl;

    return 0;
}

这段代码的作用是计算给定矩形区域中，由字符'F'组成的最大矩形面积。代码首先读取输入的矩形区域的大小，并将其表示为一个二维字符数组a。然后，通过两次遍历矩形区域的每一行，计算每个字符为'F'时，向上的连续'F'字符所对应的最左边界和最右边界。

接下来，代码使用悬线算法来计算矩形区域的最大面积。通过遍历每个字符，如果当前字符为'F'且上方的字符也为'F'，则更新该位置的高度h、最左边界l和最右边界r。最后，通过计算每个'F'字符所对应的矩形面积，并更新最大面积ans。

最后，输出结果为最大面积的3倍。

希望以上解释对您有所帮助。如果您还有其他问题，请随时提问。

如果回答对你有帮助，请给我一个最佳答案！

Ewan-Ahiouy

学习编程中的Ben 发表于 2023-8-9 14:59
问题理解：

您想要了解悬线算法（Skyline Algorithm）的工作原理，并希望对给出的代码进行解释。您想知道 ...

出bug了

歌者文明清理员

Ewan-Ahiouy 发表于 2023-8-9 14:59
出bug了

不是，因为有 [ i ]恰好就是编辑器标签 [i][i][/i]

Ewan-Ahiouy

歌者文明清理员 发表于 2023-8-9 15:00
不是，因为有 [ i ]恰好就是编辑器标签 [i]

code标签没有封闭

歌者文明清理员

Ewan-Ahiouy 发表于 2023-8-9 15:02
code标签没有封闭

哦，本来Ben写的是 [/code]111[/code]，然后修复了脚本bug，现在改成了[code]111[code]

歌者文明清理员

Ewan-Ahiouy

歌者文明清理员 发表于 2023-8-9 15:04

一眼f12

歌者文明清理员

Ewan-Ahiouy 发表于 2023-8-9 15:05
一眼f12

真没有

陶远航

Ewan-Ahiouy 发表于 2023-8-9 15:05
一眼f12

不看看我的回答吗

学习编程中的Ben

Ewan-Ahiouy 发表于 2023-8-9 14:59
出bug了

啊啊啊啊啊啊,早就说不改了

学习编程中的Ben

给个最佳答案呗!求你了!!!

Ewan-Ahiouy

@zhangjinxuan

zhangjinxuan

《绿题》

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-9 21:14
《绿题》

？

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-9 21:14
？

好难

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-9 21:15
好难

你告诉我悬线算法是什么就好了