HDU 2870 （dp46）

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; char map[1005][1005]; int dp[1005][1005]; int l[1005]; int r[1005]; int Max; int n,m; void DP() { int i,j; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { l[j]=j; while(l[j]>=2&&dp[i][j]<=dp[i][l[j]-1]) l[j]=l[l[j]-1]; } for(j=m;j>=1;j--) { r[j]=j; while(r[j]<=m-1&&dp[i][j]<=dp[i][r[j]+1]) r[j]=r[r[j]+1]; } for(j=1;j<=m;j++) if(Max<(r[j]-l[j]+1)*dp[i][j]) Max=(r[j]-l[j]+1)*dp[i][j]; } } int main() { int i,j; while(scanf("%d%d",&n,&m)!=EOF) { Max=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>map[i][j]; } } memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(map[i][j]=='a'||map[i][j]=='w'||map[i][j]=='y'||map[i][j]=='z') dp[i][j]=dp[i-1][j]+1; } } DP(); memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(map[i][j]=='b'||map[i][j]=='w'||map[i][j]=='x'||map[i][j]=='z') dp[i][j]=dp[i-1][j]+1; } } DP(); memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(map[i][j]=='c'||map[i][j]=='x'||map[i][j]=='y'||map[i][j]=='z') dp[i][j]=dp[i-1][j]+1; } } DP(); printf("%d\n",Max); } return 0; }