HDU 1505 動態規劃(DP) City Game

分析; [HDU 1506的深化版]每輸入一行，更新一次高度，就變成了1505題的問題了．[本題深化版HDU 2870]

[cpp] 
#include<iostream>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<cstdio>  
#include<cmath>  
 
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]<m&&h[R[k]+1]>=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<<endl; 
    } 
    return 0; 
} 

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>

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]<m&&h[R[k]+1]>=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<<endl;
    }
    return 0;
}