这个题只是暴力枚举会超时,考虑优化。 对于行(y 轴),我们用双指针暴力枚举,时间复杂度是 $O(m)$ 。 对于列(x 轴),维护每一列(两个行指针间)的最值,然后用双指针枚举每一列,用单调队列维护两个列指针间的最值信息,求得矩形在 x 轴上的最长长度,然后乘以暴力枚举的 y 轴长度,时间复杂度是 $O(n)$。 最后,整体的时间复杂度是 $O(mn) \ (T(m, n) = 100mn = O(mn))$。
题目1638 [IOI 1999]矩形地块(A Strip of Land)
AAAAAAAAAA
8
评论
2022-10-19 21:29:33
|