web analytics

BZOJ3039 玉蟾宫 单调栈

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3039

分析:
这道题看复杂度大概明白好像用O(n^2)就到头了。

因为是矩阵.我们可以预处理每个点往下最多能扩展多少个方块.

之后对于单独的每一行.

我们可以用预处理的高度来维护单调递增的单调栈,
我们可以感性的理解一下。
如果维护一个单调递增的栈。意味着.前面的方块的高度。都可以往后扩展。
所以每次入站的时候要记录前面最多能扩展多少个方块。(出栈的时候可以维护)
每次出栈代表着。我这个高度的方块再往后扩展不了了。(注意单调递增)

每次出栈入栈,复杂度就相当于O(n),之后每一行都要这么维护.O(n^2)

Post a Comment

You must be logged in to post a comment.