利用网格图上空白的方格上建一个矩形的建筑。问地区中建筑物的最大面积
递推(dp)
#include <iostream> #include <cstring> #include <sstream> using namespace std; const int N=1e3+2; char a[N][N]; int n,m,up[N][N],L[N][N],R[N][N]; void solve(){ int i,j; cin>>n>>m; memset(up,0,sizeof up); memset(L,0,sizeof L); memset(R,0,sizeof R); for(i=1;i<=n;i++) for(j=1;j<=m;j++){ cin>>a[i][j]; if(a[i][j]=='F'){ L[i][j]=j ; R[i][j]=j; up[i][j]=1; } } for(i=1;i<=n;i++){ for(j=2;j<=m;j++) if(a[i][j]=='F'&&a[i][j-1]=='F') L[i][j] =L[i][j-1]; for(j=m-1;j>0;j--) if(a[i][j]=='F'&&a[i][j+1]=='F') R[i][j] =R[i][j+1]; } for(i=2;i<=n;i++) for(j=1;j<=m;j++){ if(a[i][j]=='F'&&a[i-1][j]=='F'){ up[i][j]=up[i-1][j]+1; L[i][j] =max(L[i][j],L[i-1][j]); R[i][j] =min(R[i][j],R[i-1][j]); } } int ans=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++) ans=max(ans,(R[i][j]-L[i][j]+1)*up[i][j]); cout<<3*ans<<endl; } signed main(){ int tes; cin>>tes; while(tes--) solve(); }
标签:City,int,memset,up,Game,sizeof,include,UVA1330 From: https://www.cnblogs.com/towboa/p/17321853.html