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：
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;
}
然而會超時。不優化超兩個點。
快讀 + register：超一個點。
使用單調棧（遞增）：
參考洛谷這位大佬的題解。
枚舉每一行，
然後從左到右（或者從右到左）依次入棧。
棧裡存結構體
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;
}