Skip to content

Latest commit

 

History

History
 
 

2088.Count-Fertile-Pyramids-in-a-Land

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2088.Count-Fertile-Pyramids-in-a-Land

如果我们想不重复地数金字塔,那么就必须抓住金字塔的特征。我们通过数特征来统计金字塔的数目。

我们最容易想到的是金字塔的顶尖。任何一个金字塔都有一个唯一的顶尖,我们可以考虑遍历每个格子,思考如果它作为某个金字塔的顶尖的话,可以代表哪些金字塔。显然,我们光看这个格子A本身是不充分,我们得看它往下一格B,查看B是否为一个长度为3的区间的中点;再查看B的下一格C,查看C是否为一个长度为5的区间的中点... 直至类似的规律不能再持续下去。我们往下几行,就意味着A可以是几个不同金字塔的塔尖。不过这样的时间复杂度将会是o(MMN).

我们注意到,上述方法时间复杂度高是因为我们站在top,无法了解bottom的情况,所以才需要逐层下沉去调查。举个例子,我们知道某点A是一个三层金字塔的顶,那么它是否也是一个四层金字塔的顶呢?我们不知道,得下沉了才知道。

那么反过来会怎么样呢?我们站在下层,是否能知道上层的情况呢?这其实是可行的。比如说,我们站在某点A,如果知道它是一个三层金字塔的底座中点,那么我们就一定知道A也同时是一个二层金子它的底座中点。这样,如果考察每个点作为金字塔底座中点的情况,那么我们就不需要向上调查就能知道它可以对应几个不同的金字塔。这就方便多了。

那么对于任意一点A,我们如何可以知道它最大可以是多少层金字塔的底座中点呢?首先,我们要知道它自身可以是一个多长连续区间的中点。这个可以通过从左往右、从右往左两遍预处理得到。其次我们知道,如果A想成为一个三层金字塔的底座中点,那么A上面的那个格子B必须至少是一个两层金字塔的底座中点。所以我们对于A对应底座半径就有了如下的表达式:

dp(A) = min(left(A), right(A), dp(B)+1)

其中dp表示最大金字塔的底座半径,left表示A往左边最多连续多少个1,right表示A往右边最多连续多少个1.

注意最终答案不能包括层数为1的金字塔,所以答案是累加所有格子的dp值减1.