P2491 玉蟾宮
時間限制: 1 s
空間限制: 64000 KB
題目等級 : 大師 Master
題目描述 Description
有一天丛晌，小貓rainbow和freda來到了湘西張家界的天門山玉蟾宮访敌，玉蟾宮宮主藍兔盛情地款待了它們菱属，并賜予它們一片土地。
這片土地被分成N*M個格子省咨，每個格子里寫著'R'或者'F'，R代表這塊土地被賜予了rainbow，F(xiàn)代表這塊土地被賜予了freda鸣剪。
現(xiàn)在freda要在這里賣萌。。筐骇。它要找一塊矩形土地债鸡，要求這片土地都標著'F'并且面積最大。
但是rainbow和freda的OI水平都弱爆了铛纬，找不出這塊土地厌均，而藍兔也想看freda賣萌（她顯然是不會編程的……），所以它們決定告唆，如果你找到的土地面積為S棺弊，它們每人給你S兩銀子。
輸入描述 Input Description
第一行兩個整數(shù)N,M擒悬，表示矩形土地有N行M列模她。
接下來N行，每行M個用空格隔開的字符'F'或'R'懂牧，描述了矩形土地侈净。
輸出描述 Output Description
輸出一個整數(shù)，表示你能得到多少銀子归苍，即(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
數(shù)據(jù)范圍及提示 Data Size & Hint
對于50%的數(shù)據(jù)，1<=N,M<=200
對于100%的數(shù)據(jù)拼弃，1<=N,M<=1000
題解
如果用單純的暴力搜索夏伊，可得其復雜度為O(n^4)，顯然是會TLE的吻氧，所以我們應用DP來優(yōu)化
網(wǎng)上有其他神犇用單調(diào)棧優(yōu)化的O(n3)做法溺忧，而顯然我這種蒟蒻是無法參透的，我在這里要講的是一種線性DP做法盯孙，優(yōu)化后復雜度O(n2)
首先我們對于每個標記為F的點(i,j)維護兩個數(shù)組l[i][j]和r[i][j]鲁森，l[i][j]表示(i,j)這個點向左擴展最遠能到達的點的列坐標-1，r[i][j]維護(i,j)這個點向右擴展最遠能到達的點的列坐標+1振惰，若該點被標記為R歌溉，則l[i][j]=0，r[i][j]=m+1
在這里我們計算面積的思路是每次算出以(i,j)點所在行為底的最大矩形面積骑晶，所以要再維護兩個數(shù)組L[i][j]和R[i][j]痛垛，表示該點所在矩形的底的左右端點的列坐標，h[i][j]維護該矩形高桶蛔，此時狀態(tài)轉(zhuǎn)移方程顯而易見：
L[i][j]=max(l[i][j]+1,L[i-1][j]);
R[i][j]=min(r[i][j]-1,R[i-1][j]);
h[i][j]=h[i-1][j]+1;
我們在維護一個ans初始值為0匙头，每次算出一個面積值，若大于ans則進行更新仔雷，最后直接輸出ans*3即可蹂析，代碼如下
C++代碼
/*
Name:Toad Palace
Copyright:Ricardo_Y_Li
Author:Ricardo_Y_Li
Date: 09/07/17 21:23
Description:NULL
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
bool map[1010][1010];
int l[1010][1010],r[1010][1010];
int L[1010][1010],R[1010][1010],h[1010][1010];
int n,m,ans=0;
int main(){
ios::sync_with_stdio(false);
memset(map,0,sizeof(map));
memset(h,0,sizeof(h));
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char c;
cin>>c;
if(c=='F')
map[i][j]=1;
}
for(int i=1;i<=n;i++){
int t=0;
for(int j=1;j<=m;j++){
if(map[i][j])
l[i][j]=t;
else{
L[i][j]=0;
t=j;
}
}
t=m+1;
for(int j=m;j>=1;j--){
if(map[i][j])
r[i][j]=t;
else{
R[i][j]=m+1;
t=j;
}
}
}
for(int i=1;i<=m;i++){
R[0][i]=m+1;
L[0][i]=0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(map[i][j]){
h[i][j]=h[i-1][j]+1;
L[i][j]=max(l[i][j]+1,L[i-1][j]);
R[i][j]=min(r[i][j]-1,R[i-1][j]);
int s=(R[i][j]-L[i][j]+1)*h[i][j];
if(ans<s)
ans=s;
}
}
cout<<ans*3;
return 0;
}
