第二场已经做过一个类似的了,到这里只是稍微变了一下。
题意
给你一个01矩阵,让求全1矩阵的个数,但是这些矩阵中不能互相有包含关系。
思路
我们可以先用基本的单调栈求出每个(i,j)点左延伸和右延伸的地方。至于判断的话,我们想一下,所有的包含也就是上下包含和左右包含,不管多么复杂的矩阵包含无外乎都是这样的,然后左右包含,我们就看看这一行中的左延伸点和右延伸点是否相同就行,上下包含,就需要看$$l[i][j]与l[i+1][j] ,r[i][j] 与 r[i+1][j], h[i][j]与h[i+1][j] $$的关系了。
1 |
|