洛谷4147 玉蟾宫

题目背景

有一天，小猫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：

说明

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

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

题解

超时n³算法

n^3算法很好想，首先要进行一个预处理，以样例为例:
首先,读入之后将字符'F'设为1，'R' 设为0，那么样例处理之后效果如下：

0 1 1 1 1 1
1 2 2 2 2 2
1 2 2 3 3 3
2 3 3 4 4 4
3 4 4 5 5 5

然后进行n^3模拟即可，在这里不多介绍。

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<iostream>
 6 #include<algorithm>
 7 #pragma GCC optimize(1)
 8 #pragma GCC optimize(2)
 9 #pragma GCC optimize(3)
10 #include<bits/stdc++.h>
11 
12 using namespace std;
13 
14 int n,m;
15 int ans=-1;
16 int a[1050][1050];
17  
18 void init() {
19     char c;
20     scanf("%d%d",&n,&m);
21     for(int i=1; i<=n; i++)
22         for(int j=1; j<=m; j++) {
23             cin>>c;
24             if(c=='F')a[i][j]=1;
25         }
26     for(int i=1; i<=n; i++)
27         for(int j=1; j<=m; j++)
28             a[i][j]+=a[i-1][j];
29     return ;
30 }
31 
32 void out() {
33     for(int i=1; i<=n; i++) {
34         for(int j=1; j<=m; j++)
35             printf ("%d ",a[i][j]);
36         cout<<endl;
37     }
38     return;
39 }
40 
41 void work() {
42     //out(); 
43     for(int i=1; i<=n; ++i)
44         for(int j=1; j<=i; j++) {
45             int sum=0;
46             for(int k=1; k<=m; ++k) {
47                 if(a[i][k]-a[j-1][k]==i-j+1)
48                     sum+=a[i][k]-a[j-1][k],ans=max(ans,sum);
49                 else sum=0;
50             }
51         }
52     cout<<ans*3<<endl;
53     return;
54 }
55 
56 int main() {
57     init();
58     work();
59     return 0;
60 }

代码中可以看到，我同时开了O1,O2,O3优化，但是仍然没有逃脱超时的命运。

满分算法

我们考虑使用单调栈。关于单调栈，我推荐一篇博客：

https://www.cnblogs.com/COLIN-LIGHTNING/p/8474668.html

这篇博客很良心，博主是我在博客园中唯一关注的。

那下面还是从头讲本题正解：

1.我们按行去划分，O(n)枚举行，对该行即以上的部分做最大矩阵处理；

2.那么我们用pos数组记录每行向上可延伸的最大距离，预处理的方式即为：

(1)读到一个‘F’，该处a=上一行该列a的值+1；

(2)读到一个‘R’，该处a=0（因为该处不可向上伸展）；

（以上都是n^3超时算法也要处理的）

3.那么对于每次枚举:对该行及以上的部分从左往右或从右往左进行一次单增栈，每次弹栈时更新最大面积;

(1)首先，该栈是单调递增的

(2)如果入栈元素小于栈顶元素，栈顶元素就要出栈

(3)如果入栈元素不小于栈顶元素，那么先入栈，然后计算当前的最大面积，更新本组答案。

4.对每次枚举的最大面积取max即为最终答案；

 1 #include <stack>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <bits/stdc++.h>
 7 using namespace std;
 8 
 9 const int N=1005;
10 
11 int n,m,ans=0;
12 int a[N][N];
13 stack <int> s,L;
14 
15 void init()
16 {
17     int i,j;
18     char ch[2];
19     scanf("%d %d",&n,&m);
20     for (i=1; i<=n; i++)
21         for(j=1; j<=m; j++)
22         {
23             scanf("%s",ch);
24             if (ch[0]=='F')
25                 a[i][j]=a[i-1][j]+1;//a[i][j]表示第j列从第i行往上'F'的个数(高度)
26         }
27 }
28 
29 void work(int h[])//处理到第i行
30 {
31     int j,len;
32     s.push(0);//栈内保存高度
33     L.push(0);//栈内保存宽度
34     for(j=1; j<=m; j++)
35         if (h[j]>=s.top())
36         {
37             s.push(h[j]);
38             L.push(1);
39         }
40         else
41         {
42             len=0;
43             while(!s.empty() && s.top()>h[j])//高度栈保证单调递增
44             {
45                 len+=L.top();
46                 ans=max(ans,len*s.top());
47                 s.pop();
48                 L.pop();
49             }
50             s.push(h[j]);
51             L.push(len+1);
52         }
53     len=0;
54     while(!s.empty())//最后计算答案
55     {
56         len+=L.top();
57         ans=max(ans,len*s.top());
58         s.pop();
59         L.pop();
60     }
61 }
62 
63 int main()
64 {
65     init();
66     for(int i=1; i<=n; i++)
67         work(a[i]);
68     printf("%d
",3*ans);
69     return 0;
70 }

出处：https://www.cnblogs.com/yujustin/

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

温馨提示：尽量使用版本较高的浏览器，并打开极速模式。