POJ2796 - Feel Good - 단조로운 대기열(dp사상)

1. 제목 설명:
Feel Good
Time Limit: 3000MS
 
Memory Limit: 65536K
Total Submissions: 14381
 
Accepted: 3976
Case Time Limit: 1000MS
 
Special Judge
Description
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

Source
Northeastern Europe 2005
2. 주제 개요:
구간을 드리려면 (이 구간과 같은 최소값 * 이 구간의 모든 원소의 합) 의 최대값을 구해야 합니다.
예를 들면 다음과 같습니다.

6
3 1 6 4 5 2

4를 최소값으로 하고 좌우로 뻗으며 6 4 5를 60으로 한다
3. 문제를 푸는 사고방식:
각 점이 최소값으로 양쪽으로 뻗는 최대 길이를 고려하여 그보다 큰 값(보다 작은)을 만나면 그 뻗는 범위를 확대한다. 일반적으로 이렇게 하는 알고리즘의 복잡도는 o(n^2)이다.그러나 창고라는 장난감을 빌려 단조로운 증가(감소)를 유지하면 o(n)의 시간 복잡도에서 이 문제를 해결할 수 있다.원소를 창고에 넣을 때, 먼저 원소가 창고 꼭대기 원소보다 크는지, 창고 꼭대기 원소보다 크면 창고에 넣는지 판단합니다.(여기서부터 단조로운 창고 유지만 말한다) 그렇지 않으면 창고 꼭대기 요소를 창고에서 꺼내서 창고 꼭대기 요소가 창고에 들어갈 요소보다 작을 때까지 유지해야 한다. 이 과정에서 앞으로 뻗거나 뒤로 뻗는 문제를 유지해야 한다. 창고에 들어갈 원소가 들어가기 전에 n개의 창고 원소가 창고에서 나오면 이 n개의 창고 원소가 창고에 들어갈 원소보다 크거나 같다는 뜻이다. 이때우리는 입고 요소가 앞으로 몇 개의 요소를 연장할 수 있는지 유지해야 한다. (입고 요소가 그것보다 얼마나 큰지 기록하는 것과 같다.) 그리고 모든 창고 꼭대기 요소는 출고된 요소로 연장해야 한다. 왜냐하면 출고된 요소는 반드시 그것보다 큰 요소이기 때문이다. (내가 유지하는 것은 단조로운 증고이다.)이렇게 하면 o(n)의 시간 복잡도 내에서 상술한 문제를 해결하였다.
예: 3 1 6 4 5 2
(3,1,1)  (1,2,2)  (6,3,3)  (4,4,4)  (5,5,5)  (2,6,6)
우선 각 원소 자체의 앞뒤 연장은 1이다. 3을 창고에 넣고 1<3, 3을 창고에서 꺼내고 1의 앞 연장에 3의 앞 연장을 더하면 이렇게 (1, 1, 2), 6<1, 창고에 넣고 (1, 1, 2)(6, 3, 3),
4<6, 6을 출고하고 4를 앞으로 뻗고 1을 뒤로 뻗어 (1, 1, 3)(4, 3, 4)
5>4, 입고, (1,1,3)(4,3,4)(5,5,5)
2<5, 5 출고, 2 앞으로 뻗고, 4 뒤로 뻗고, (1, 1, 3)(4, 3, 5)2 아직 입고하지 않음(2, 5, 6)
2<4, 4출고, 2는 앞으로 뻗고, 1은 뒤로 뻗고, (1, 1, 5)(2, 3, 6)로 변한다.
한 번 유추하면 가장 큰 결과가 (4,3,5)라는 것을 발견할 수 있다. 이것은 4를 최소치로 하는 구간 범위가 3--5, 즉 64, 5라는 것을 의미한다.AC 코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include