【NOIP模拟赛】土豪聪要请客

2014年10月23日1,3023

众所周知,聪哥(ndsf)是个土豪,不过你们不知道的是他的MZ和他的RMB一样滴多……

某天土豪聪又赚了10^10000e的RMB,他比较开心,于是准备请客。他在自己在XX星上的别墅里面大摆酒席,想要邀请尽可能多的MZ来参加他的宴会。他将会同MZ一起坐在一个巨大的长方形桌子上。这个桌子能坐下的人数等于他的边长。聪哥要求他的桌子能够放进他的别墅,并且桌子的边必须与别墅的边界平行。给定别墅的平面图,请你求出聪哥最多可以请多少个MZ。

 

输入格式

第一行n,m。表示别墅的长宽

下面n行,每行M个字符,表示一个方块是空的(‘ ’)或是被占用了(‘X’)。

聪哥只要他的桌子放在别墅里,并且桌子不能占用任何一个已经占用了的方块。

 

输出格式

一个数,表示聪哥最多可以请几个Maze。

 

样例输入1

2 2

..

..

 

样例输出1

7

 

样例输入2

4 4

X.XX

X..X

..X.

..XX

 

样例输出2

9

 

对于60%的数据,n,m<=100

对于100%的数据,n,m<=400

 

题解

首先预处理每个格子向左拓展的最大长度f[i][j]

然后枚举上下边界l,r。。。然后枚举列x,则min{f[i][x]}(l<=i<=r)与r-l+1构成的长方形可以更新答案

复杂度n^4

或者用相同的预处理方法,枚举每个格子i,j

以f[i][j]为宽向上下拓展 ,拓展到极大时(r-l+1)与f[i][j]可以更新答案

然后f[i][j]–,继续拓展,以此类推,复杂度n^3

或者按最大01子矩阵那样用前缀和来搞好像也是n^3
似乎有n^2做法?

顺便贴个数据生成器

 

  • 幸京睿2015年10月30日 下午9:31 回复

    可以解释一下样例吗?请问什么叫“这个桌子能坐下的人数等于他的边长”,边长是啥意思?

    #1  
    • hzwer2015年10月31日 下午1:46 回复

      周长

      #11
      • 小蒟蒻2015年11月1日 下午2:19 回复

        哦,周长啊,谢黄学长

        #12