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;
}
补充：软件开发 , C++ ,
