本文共 2802 字，大约阅读时间需要 9 分钟。

J - Feel Good

Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to studying how good or bad days influent people’s memories about some period of life.

A new idea Bill has recently developed assigns a non-negative integer value to each day of human life.

Bill calls this value the emotional value of the day. The greater the emotional value is, the better the daywas. Bill suggests that the value of some period of human life is proportional to the sum of the emotional values of the days in the given period, multiplied by the smallest emotional value of the day in it. This schema reflects that good on average period can be greatly spoiled by one very bad day.

Now Bill is planning to investigate his own life and find the period of his life that had the greatest value. Help him to do so.

Input The first line of the input contains n - the number of days of Bill’s life he is planning to investigate(1 <= n <= 100 000). The rest of the file contains n integer numbers a1, a2, … an ranging from 0 to 10 6 - the emotional values of the days. Numbers are separated by spaces and/or line breaks. Output Print the greatest value of some period of Bill’s life in the first line. And on the second line print two numbers l and r such that the period from l-th to r-th day of Bill’s life(inclusive) has the greatest possible value. If there are multiple periods with the greatest possible value,then print any one of them. Sample Input 6 3 1 6 4 5 2 Sample Output 60 3 5

题意就是让你找一个区间，找出区间数的和乘上区间最小值的最大值，输出这个最大值以及区间的左端点和右端点。

说一下直观的理解，直接枚举每个区间肯定是不行的，那么是否可以发现某些性质减少枚举的次数呢？这是显然有的。对于每个数，如果一个区间里要选这个数，且这个数是当前区间的最小值，那么什么时候是最优的呢？显然是找出以这个数为最小值的区间，加上这个区间内的所有数，这样和可能变大，且最小值不变，显然更优。这个题用就是用单调栈来找出来每个数为最小值的区间。 下面说一下做法： (1)当前的值大于栈头，就入栈。 (2)当前值小于栈头，就弹出栈头到栈头小于当前值，在弹出的过程中，弹出的值全部 >= 当前值，假设一直弹到了 stk [ tt ] < 当前值，那么 tt + 1 ~ 当前坐标 即为当前值为最小值的前半区间。 每次更新的时候紧接着更新答案即可。 可以在 a 后面加一个 -1 来充当最小值以免栈中存留未计算的元素。 还有要注意一下 ans 初始值要设为 -1 ，因为他的和可能为 0 ，这样虽然 ans 是对的，但是更新不了区间，wa了好几发才看出来。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105980358 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！