P4147 玉蟾宫
一道难题
题目背景
有一天，小猫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：
1
2
3
4
5
6
| 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
思路
用一个二维的s数组储存第i行j列的F的上面包括自己有多少个F
然后遍历每一格，往左右延伸，找到最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include<cstdio>
#include<iostream>
using namespace std;
int n,m;
const int MAXN=1000+5;
int s[MAXN][MAXN];
inline void read(int &x){
x=0;
register short k=1;
register char t=getchar();
while(t>'9'||t<'0'){
if(t=='-')k=-k;
t=getchar();
}
while(t>='0'&&t<='9'){
x*=10;
x+=(t-'0');
t=getchar();
}
x*=k;
}
int main(){
read(n);
read(m);
char tmp;
for(register int i=1;i<=n;++i){
for(register int j=1;j<=m;++j){
tmp=getchar();
while(tmp!='F'&&tmp!='R')tmp=getchar();
if(tmp=='F'){
s[i][j]=s[i-1][j]+1;
}
}
}
int ans=0;
for(register int i=1;i<=n;++i){
for(register int j=1;j<=m;++j){
register int l=j,r=j;
while(l>=1&&s[i][l]>=s[i][j])--l;
while(r<=m&&s[i][r]>=s[i][j])++r;
++l;
--r;
ans=max(ans,3*(s[i][j]*(r-l+1)));
}
}
printf("%d\n",ans);
return 0;
}
|
然而会超时。不优化超两个点。
快读+register：超一个点。
使用单调栈（递增）：
参考洛谷这位大佬的题解。
枚举每一行，
然后从左到右（或者从右到左）依次入栈。
栈里存结构体
1
2
3
4
5
6
| struct node
{
int kuan,gao;
}
|
然后每次入栈的元素的宽设为它弹出的元素的宽度和+1。
因为弹出的都冲得比他高（或者同样高）
用tmp变量记录弹出的宽度总和
每弹一次，求弹掉的高*tmp，取最大值
全部入过栈之后，全部弹出。重算tmp和弹掉的高*tmp，继续取最大值。
所有行的最大值的最大值*3为答案。。。。。。
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<iostream>
using namespace std;
int n,m;
const int MAXN=1000+5;
int s[MAXN][MAXN]= {{0}};
struct node
{
int kuan,gao;
} st[MAXN];
int tp,sz;
inline void read(int &x)
{
x=0;
register short k=1;
register char t=getchar();
while(t>'9'||t<'0')
{
if(t=='-')k=-k;
t=getchar();
}
while(t>='0'&&t<='9')
{
x*=10;
x+=(t-'0');
t=getchar();
}
x*=k;
}
int main()
{
read(n);
read(m);
char tmp;
for(register int i=1; i<=n; ++i)
{
for(register int j=1; j<=m; ++j)
{
tmp=getchar();
while(tmp!='F'&&tmp!='R')tmp=getchar();
if(tmp=='F')
{
s[i][j]=s[i-1][j]+1;
}
}
}
int ans=0;
for(int i=1; i<=n; ++i)
{
int maxs=0;
st[1].gao=s[i][1];
st[1].kuan=1;
tp=1;
for(int j=2;j<=m;++j){
int tmp=0;
while(st[tp].gao>=s[i][j]&&tp){
tmp+=st[tp].kuan;
maxs=max(maxs,st[tp].gao*tmp);
--tp;
}
++tp;
st[tp].gao=s[i][j];
st[tp].kuan=tmp+1;
}
int tmp=0;
while(tp){
tmp+=st[tp].kuan;
maxs=max(maxs,st[tp].gao*tmp);
--tp;
}
ans=max(ans,maxs);
}
printf("%d\n",3*ans);
return 0;
}
|
