不理解悬线算法

Ewan-Ahiouy

rt

这有个案例：luogu P4147

my code

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int MAXN = 1010;
   
5. int n, m, ans, h[MAXN][MAXN], l[MAXN][MAXN], r[MAXN][MAXN];
   
6. char a[MAXN][MAXN];
   
7. 
   
8. int main() {
   
9.     ans = 0;
   
10.     cin >> n >> m;
    
11.     for (int i = 1; i <= n; i++) {
    
12.         for (int j = 1; j <= m; j++) {
    
13.             cin >> a[i][j];
    
14.             h[i][j] = 1, r[i][j] = l[i][j] = j;
    
15.         }
    
16.         for (int j = 2; j <= m; j++) if (a[i][j] == 'F' && a[i][j - 1] == 'F') l[i][j] = l[i][j - 1];
    
17.         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];
    
18.     }
    
19.     for (int i = 1; i <= n; i++)
    
20.         for (int j = 1; j <= m; j++) {
    
21.             if (i > 1 && a[i][j] == 'F') {
    
22.                 if (a[i - 1][j] == 'F') {
    
23.                     h[i][j] = h[i - 1][j] + 1;
    
24.                     if (l[i - 1][j] > l[i][j]) l[i][j] = l[i - 1][j];
    
25.                     if (r[i - 1][j] < r[i][j]) r[i][j] = r[i - 1][j];
    
26.                 }
    
27.                 if ((r[i][j] - l[i][j] + 1) * h[i][j] > ans) ans = (r[i][j] - l[i][j] + 1) * h[i][j];
    
28.             }
    
29.         }
    
30.     cout << 3 * ans << endl;
    
31. 
    
32.     return 0;
    
33. }

复制代码

不理解怎么可以这样写

大佬能帮忙解释一下吗？

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]）
累加起来输出就好了

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<stack>
   
4. #define int long long
   
5. 
   
6. using namespace std;
   
7. const int Max = 1005;
   
8. int f[Max][Max];
   
9. int a[Max];
   
10. int r[Max],l[Max];
    
11. signed main()
    
12. {
    
13.         char c;
    
14.         int n,m;
    
15.         cin >> n >> m;
    
16.         for(register int i = 1;i <= n;++ i)
    
17.         {
    
18.                 for(register int j = 1;j <= m;++ j)
    
19.                 {
    
20.                         cin >> c;
    
21.                         if(c == '*')f[i][j] = 0;
    
22.                         else
    
23.                         f[i][j] = f[i - 1][j] + 1;
    
24.                 }
    
25.         }
    
26.         for(int i = 1;i <= n;++ i)
    
27.                 f[i][0] = f[i][m + 1] = -0x7fffffff;
    
28.         int ans = 0;
    
29.         for(register int i = 1;i <= n;++ i)
    
30.         {
    
31.                 stack<int>s1,s2;
    
32.                 s1.push(1),s2.push(m);
    
33.                 for(register int ii = 2,jj = m - 1;ii <= m + 1,jj >= 0;jj --,++ ii)
    
34.                 {
    
35.                         while(!s1.empty() && f[i][ii] < f[i][s1.top()])
    
36.                         {
    
37.                                 r[s1.top()] = ii;
    
38.                                 s1.pop();
    
39.                         }
    
40.                         while(!s2.empty() && f[i][jj] <= f[i][s2.top()])
    
41.                         {
    
42.                                 l[s2.top()] = jj;
    
43.                                 s2.pop();
    
44.                         }
    
45.                         s1.push(ii);s2.push(jj);
    
46.                 }
    
47.                 for(register int j = 1;j <= m;++ j)
    
48.                         ans += (j - l[j]) * (r[j] - j) * f[i][j];
    
49.         }
    
50.         cout << ans << endl;
    
51.         return 0;
    
52. }

复制代码

Mike_python小

问题理解：

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

解决方案：

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

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

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

复制代码

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

2. int main() {
3.     ans = 0;
4.     cin >> n >> m;
6.     for (int i = 1; i <= n; i++) {
7.         for (int j = 1; j <= m; j++) {
8.             cin >> a[i][j];
9.             h[i][j] = 1, r[i][j] = l[i][j] = j;
10.         }
11.         
12.         for (int j = 2; j <= m; j++)
13.             if (a[i][j] == 'F' && a[i][j - 1] == 'F')
14.                 l[i][j] = l[i][j - 1];
15.                
16.         for (int j = m - 1; j > 0; j--)
17.             if (a[i][j] == 'F' && a[i][j + 1] == 'F')
18.                 r[i][j] = r[i][j + 1];
19.     }

复制代码

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

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

2.     for (int i = 1; i <= n; i++) {
3.         for (int j = 1; j <= m; j++) {
4.             if (i > 1 && a[i][j] == 'F') {
5.                 if (a[i - 1][j] == 'F') {
6.                     h[i][j] = h[i - 1][j] + 1;
7.                     if (l[i - 1][j] > l[i][j])
8.                         l[i][j] = l[i - 1][j];
9.                     if (r[i - 1][j] < r[i][j])
10.                         r[i][j] = r[i - 1][j];
11.                 }
12.                 if ((r[i][j] - l[i][j] + 1) * h[i][j] > ans)
13.                     ans = (r[i][j] - l[i][j] + 1) * h[i][j];
14.             }
15.         }
16.     }

复制代码

这部分是算法的主要部分。它使用动态规划的思想，计算了每个位置（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）的工作原理，并希望对给出的代码进行解释。您想知道如何理解这段代码，并希望得到完整修改后的代码。

解决方案：

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

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

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. const int MAXN = 1010;
   
5. int n, m, ans, h[MAXN][MAXN], l[MAXN][MAXN], r[MAXN][MAXN];
   
6. char a[MAXN][MAXN];
   
7. 
   
8. int main() {
   
9.     ans = 0;
   
10.     cin >> n >> m;
    
11. 
    
12.     // 读取矩形区域的字符表示
    
13.     for (int i = 1; i <= n; i++) {
    
14.         for (int j = 1; j <= m; j++) {
    
15.             cin >> a[i][j];
    
16.             h[i][j] = 1, r[i][j] = l[i][j] = j;
    
17.         }
    
18.         // 计算每一行内，连续的F字符所对应的最左边界和最右边界
    
19.         for (int j = 2; j <= m; j++) {
    
20.             if (a[i][j] == 'F' && a[i][j - 1] == 'F')
    
21.                 l[i][j] = l[i][j - 1];
    
22.         }
    
23.         for (int j = m - 1; j > 0; j--) {
    
24.             if (a[i][j] == 'F' && a[i][j + 1] == 'F')
    
25.                 r[i][j] = r[i][j + 1];
    
26.         }
    
27.     }
    
28. 
    
29.     // 使用悬线算法计算矩形区域的最大面积
    
30.     for (int i = 1; i <= n; i++) {
    
31.         for (int j = 1; j <= m; j++) {
    
32.             if (i > 1 && a[i][j] == 'F') {
    
33.                 if (a[i - 1][j] == 'F') {
    
34.                     h[i][j] = h[i - 1][j] + 1;
    
35.                     if (l[i - 1][j] > l[i][j])
    
36.                         l[i][j] = l[i - 1][j];
    
37.                     if (r[i - 1][j] < r[i][j])
    
38.                         r[i][j] = r[i - 1][j];
    
39.                 }
    
40.                 if ((r[i][j] - l[i][j] + 1) * h[i][j] > ans)
    
41.                     ans = (r[i][j] - l[i][j] + 1) * h[i][j];
    
42.             }
    
43.         }
    
44.     }
    
45. 
    
46.     cout << 3 * ans << endl;
    
47. 
    
48.     return 0;
    
49. }
    

复制代码

这段代码的作用是计算给定矩形区域中，由字符'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
好难

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