先上题目:
Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 4101 Accepted
Submission(s): 1710
1 #include <cstdio> 2 #include <cstring> 3 #define MAX 1002 4 #define max(x,y) (x > y ? x : y) 5 using namespace std; 6 7 bool map[MAX][MAX]; 8 int cx[MAX][MAX]; 9 int l[MAX],r[MAX]; 10 11 int main() 12 { 13 int n,m,t,maxn; 14 char c[2]; 15 //freopen("data.txt","r",stdin); 16 scanf("%d",&t); 17 getchar(); 18 while(t--){ 19 scanf("%d %d",&n,&m); 20 getchar(); 21 for(int i=1;i<=n;i++){ 22 for(int j=1;j<=m;j++){ 23 scanf("%s",c); 24 if(c[0]==‘R‘) map[i][j]=0; 25 else map[i][j]=1; 26 } 27 } 28 memset(cx,0,sizeof(cx)); 29 30 for(int i=1;i<=n;i++){ 31 for(int j=1;j<=m;j++){ 32 if(map[i][j]){ 33 cx[i][j]=cx[i-1][j]+1; 34 } 35 } 36 } 37 38 maxn=0; 39 for(int i=1;i<=n;i++){ 40 41 cx[i][0]=cx[i][m+1]=-1; 42 43 for(int j=1;j<=m;j++){ 44 l[j]=r[j]=j; 45 } 46 47 for(int j=2;j<=m;j++){ 48 while(cx[i][j]<=cx[i][l[j]-1]){ 49 l[j]=l[l[j]-1]; 50 } 51 } 52 53 for(int j=m-1;j>=1;j--){ 54 while(cx[i][j]<=cx[i][r[j]+1]){ 55 r[j]=r[r[j]+1]; 56 } 57 } 58 59 for(int j=1;j<=m;j++){ 60 int ans=cx[i][j]*(r[j]-l[j]+1); 61 maxn=max(ans,maxn); 62 } 63 } 64 printf("%d\n",maxn*3); 65 } 66 return 0; 67 }
HDU - 1505 - City Game,布布扣,bubuko.com
原文:http://www.cnblogs.com/sineatos/p/3600364.html