poj 2796 Feel Good (前缀和,单调栈)

poj 2796

题意:给出一个人n(1E5)天的情绪值(0..1E6),一段时间的value的定义是这段时间的情绪之和*这段时间情绪的最小值。

现在求value的最大值,并且输出得到这个最大值的区间。

思路:单调栈。 考虑把每一天作为最小值的时候能向左向由延伸的最远的点的下标,两[……]

Read more

poj 2082 Terrible Sets (前缀和,单调栈)

poj 2082 题目链接

题意:这道题简直就是。。。教给大家怎么把一句话把简单的题让人出得看不懂。。。真的一点意思都没有。给出n个矩形的宽度和高度,这些矩形并排顺次排列在x轴上,问最大面积。

思路:单调栈。 之前的最大矩形面积的宽度都是1.。这次不是1.。做个宽度的前缀和就好。。。1A[……]

Read more

poj 3250 Bad Hair Day(单调栈)

poj 3250

题意:

n头牛排成一列,第n只牛在最前面,第1只牛在最后面。第i只牛能看到的牛的个数是,它前面的且没有被其他牛遮挡的牛的个数,遮挡的条件是高度大于或者相同。现在问所有牛能看到的牛的个数的和。

思路:单调栈。具体见代码。1A.

[crayon-5a8e8[……]

Read more

poj 2559 Largest Rectangle in a Histogram (单调栈)

poj 2559

题意:给定从左到右多个矩形,已知这此矩形的宽度都为1,长度不完全相等。这些矩形相连排成一排,求在这些矩形包括的范围内能得到的面积最大的矩形,求该面积。所求矩形可以横跨多个矩形,但不能超出原有矩形所确定的范围。

思路:单调栈。。。好久没写了,感觉之前一直也没有完全掌握单调[……]

Read more