P4147 玉蟾宫#
一つの難問
問題の背景#
ある日、小猫の rainbow と freda は湘西張家界の天門山玉蟾宮にやってきました。玉蟾宮の宮主である藍兎は彼らを親切にもてなし、彼らに土地を与えました。
問題の説明#
この土地は N*M のグリッドに分割されており、各グリッドには 'R' または 'F' と書かれています。R はこの土地が rainbow に与えられたことを示し、F はこの土地が freda に与えられたことを示します。
今、freda はここでかわいく見せたい... 彼女は F が書かれた長方形の土地を探し、その土地が最大であることを求めます。
しかし、rainbow と freda の OI レベルはとても低く、この土地を見つけることができません。藍兎も freda がかわいく見せるのを見たいです（彼女は明らかにプログラミングはできません...）。だから、もし見つけた土地の面積が S であるなら、彼らはそれぞれ S の銀貨をあげます。
入出力の形式#
入力の形式：
最初の行には N と M の 2 つの整数があり、それは長方形の土地が N 行 M 列あることを示しています。
次の N 行には、各行に M 個のスペースで区切られた文字 'F' または 'R' があり、長方形の土地を説明しています。
出力の形式：
1 つの整数を出力し、得られる銀貨の量を表します。つまり、(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：
45
説明#
50% のデータに対して、1 <= N, M <= 200
100% のデータに対して、1 <= N, M <= 1000
アイデア#
二次元配列sを使用して、第i行j列のFの上にあるFの数を保存します。
そして、各グリッドを走査し、最大値を見つけます。
#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;
}
しかし、時間制限を超えてしまいます。2 つ以上の点を最適化する必要があります。
高速入力 + register：1 つの点を超えます。
単調増加スタックを使用する：
洛谷のこの方の解説を参考にしました。
各行を列挙し、
左から右（または右から左）に順番にスタックに入れます。
スタックには構造体を保存します。
struct node
{
int kuan,gao;
}
//kuanは左右に延長できる長さ（幅）
//gaoは上に伸びる高さ
次にスタックに入れる要素の幅を、ポップした要素の幅 + 1 に設定します。
なぜなら、ポップされた要素は彼よりも高く上がっているからです（または同じ高さです）
tmp 変数にポップされた幅の合計を記録します
ポップするたびに、ポップされた高さ * tmp を求め、最大値を取ります
すべての要素がスタックに入ったら、すべてをポップします。tmp とポップされた高さ * tmp を再計算し、最大値を取ります。
すべての行の最大値の最大値 * 3 が答えです。。。。。。
完全なコード
#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;
}