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

poj 2796

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

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

思路:单调栈。 考虑把每一天作为最小值的时候能向左向由延伸的最远的点的下标,两个方向各做一次单调栈来预处理。和的haunted前缀和搞下。。

然后最后想着了LL,但是读入的时候前缀和的那里忘了LL wa了一发。。。2A

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz