首页 > 代码库 > [Tyvj1939] 玉蟾宫（单调栈）

[Tyvj1939] 玉蟾宫（单调栈）

2024-09-19 23:40:16   211人阅读

传送门

 

题目

Description

有一天，小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。
这片土地被分成N*M个格子，每个格子里写着’R’或者’F’，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。
现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着’F’并且面积最大。
但是rainbow和freda的OI水平都弱爆了，找不出这块土地，而蓝兔也想看freda卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为S，它们每人给你S两银子。

 

Input

第一行两个整数N,M，表示矩形土地有N行M列。
接下来N行，每行M个用空格隔开的字符’F’或’R’，描述了矩形土地。

 

Output

输出一个整数，表示你能得到多少银子，即(3*最大’F’矩形土地面积)的值。

 

Sample Input

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
 

Sample Output

45
 

HINT

对于50%的数据，1<=N,M<=200

对于100%的数据，1<=N,M<=1000

 

思路

好像没有权限号提交不了这题，不过和黄学长对拍过，应该没什么问题吧。

 

n3 肯定是不行的。

可以 n2 预处理出来每个点上面的 F 的高度，这样这张图的每一行就变成了直方图。

目的就是扫描每一行的直方图，然后计算直方图中的最大矩阵。

求直方图的最大矩阵可以用单调栈优化，l[i] 表示在 i 左边比 i 小的第一个，r[i] 表示在 i 右边比 i 小的第一个。

l 和 r 数组可以从后往前和从前往后扫两边求出来。

最后 ans = max(ans, (r[i] - l[i] - 1) * h[i]) 求出 （h[i] 为高度）

 

代码

技术分享
 1 #include <cstdio> 2 #include <iostream> 3  4 using namespace std; 5  6 const int MAXN = 1001; 7 int n, m, ans, top; 8 int a[MAXN][MAXN], s[MAXN], l[MAXN], r[MAXN]; 9 10 inline void work(int h[])11 {12     int i;13     h[0] = h[m + 1] = -1;14     top = 0;15     for(i = 1; i <= m + 1; i++)16     {17         while(top && h[s[top]] > h[i]) r[s[top--]] = i;18         s[++top] = i;19     }20     top = 0;21     for(i = m; i >= 0; i--)22     {23         while(top && h[s[top]] > h[i]) l[s[top--]] = i;24         s[++top] = i;25     }26     for(i = 1; i <= m; i++) ans = max(ans, (r[i] - l[i] - 1) * h[i]);27 }28 29 int main()30 {31     char ch[1];32     scanf("%d %d", &n, &m);33     for(int i = 1; i <= n; i++)34         for(int j = 1; j <= m; j++)35         {36             scanf("%s", ch);37             if(ch[0] == ‘F‘) a[i][j] = a[i - 1][j] + 1;38         }39     for(int i = 1; i <= n; i++) work(a[i]);40     printf("%d", ans * 3);41     return 0;42 }
View Code

 

[Tyvj1939] 玉蟾宫（单调栈）


联系
我们