HDU 1505 动态规划(DP) City Game

分析; [HDU 1506的深化版]每输入一行，更新一次高度，就变成了1505题的问题了．[本题深化版HDU 2870]

[cpp]
#include
#include
#include
#include
#include
#include

using namespace std;

int h[1005],L[1005],R[1005];

int main(){
int T; cin>>T;
while(T--){
int n,m; cin>>n>>m;
getchar();
memset(h,0,sizeof(h));
int maxs=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
char a; cin>>a;
if(a=='F')++h[j];
else h[j]=0;
L[j]=R[j]=j;
getchar();
}
for(int j=1,k=m;j<=m;++j,--k){
while(L[j]>1&&h[L[j]-1]>=h[j])
L[j]=L[L[j]-1];
while(R[k]=h[k])
R[k]=R[R[k]+1];
}
for(int j=1;j<=m;++j){
int s=h[j]*(R[j]-L[j]+1);
maxs=max(maxs,s);
}
}
cout<<3*maxs< }
return 0;
}

#include
#include
#include
#include
#include
#include

using namespace std;

int h[1005],L[1005],R[1005];

int main(){
int T; cin>>T;
while(T--){
int n,m; cin>>n>>m;
getchar();
memset(h,0,sizeof(h));
int maxs=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
char a; cin>>a;
if(a=='F')++h[j];
else h[j]=0;
L[j]=R[j]=j;
getchar();
}
for(int j=1,k=m;j<=m;++j,--k){
while(L[j]>1&&h[L[j]-1]>=h[j])
L[j]=L[L[j]-1];
while(R[k]=h[k])
R[k]=R[R[k]+1];
}
for(int j=1;j<=m;++j){
int s=h[j]*(R[j]-L[j]+1);
maxs=max(maxs,s);
}
}
cout<<3*maxs< }
return 0;
}