首页 > 代码库 > hdu 1505 City Game
hdu 1505 City Game
http://acm.hdu.edu.cn/showproblem.php?pid=1505
先处理每一行上每一个F为底往上所到达的高度,然后再左右处理。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 1001 5 using namespace std; 6 7 int t; 8 int n,m; 9 int a[maxn][maxn];10 int l[maxn],r[maxn];11 12 int main()13 {14 scanf("%d",&t);15 while(t--)16 {17 scanf("%d%d",&n,&m);18 getchar();19 memset(a,0,sizeof(a));20 for(int i=1; i<=n; i++)21 {22 for(int j=1; j<=m; j++)23 {24 char s[10];25 scanf("%s",s);26 if(s[0]==‘F‘) a[i][j]=a[i-1][j]+1;27 else a[i][j]=0;28 }29 }30 int max1=-1;31 for(int i=1; i<=n; i++)32 {33 a[i][0]=a[i][m+1]=-1;34 for(int j=1; j<=m; j++)35 l[j]=r[j]=j;36 for(int j=1; j<=m; j++)37 {38 while(a[i][j]<=a[i][l[j]-1]) l[j]=l[l[j]-1];39 }40 for(int j=m; j>=1; j--)41 {42 while(a[i][j]<=a[i][r[j]+1]) r[j]=r[r[j]+1];43 }44 for(int j=1; j<=m; j++)45 {46 int ans=a[i][j]*(r[j]-l[j]+1);47 if(ans>max1)48 max1=ans;49 }50 }51 printf("%d\n",max1*3);52 }53 return 0;54 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。