POJ2796【单调栈】

题意&＃xff1a;
题意&＃xff1a;n个数&＃xff0c;求某段区间的最小值*该段区间所有元素之和的最大值
思路&＃xff1a;
主要参考&＃xff1a;http://www.cnblogs.com/ziyi–caolu/archive/2013/06/23/3151556.html
首先我们假设第i个元素是最小的话&＃xff0c;那么他的区间是确定的&＃xff0c;所以值也是确定的。
然后就是利用栈&＃xff08;单调栈&＃xff09;&＃xff0c;对于每个位置&＃xff0c;搞一个前最远&＃xff0c;后最远&＃xff0c;然后出栈更新&＃xff0c;再入栈。
感觉就是个利用栈&＃xff0c;并且维护这个栈是从栈顶到栈底是单调递增的&＃xff0c;存了起来操作。当不是单调递增的时候&＃xff0c;栈里的值比他小的就要拿出来&＃xff0c;让他更新&＃xff0c;然后还要当前栈顶和刚刚拿出来的next更新&＃xff0c;具体看代码&＃xff1b;
PS&＃xff1a;G&＃43;&＃43;AC,C&＃43;&＃43;TLE&＃xff1b;

//#include
#include
#include
#include
using namespace std;typedef long long LL;
const int N&＃61;1e5&＃43;10;struct asd{LL pre;LL num;LL next;LL k;
};
int n;
stackq;
LL str[N],t[N];int main()
{while(!q.empty())q.pop();LL ans&＃61;-1;LL sum&＃61;-1;LL num;asd tmp;scanf("%d",&n);str[0]&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%lld",&t[i]);str[i]&＃61;str[i-1]&＃43;t[i];}tmp.num&＃61;t[1];tmp.pre&＃61;tmp.next&＃61;1;tmp.k&＃61;1;q.push(tmp);LL x&＃61;0,y&＃61;0;for(LL i&＃61;2;i<&＃61;n;i&＃43;&＃43;){asd tmp1;tmp1.num&＃61;t[i];tmp1.pre&＃61;tmp1.next&＃61;1;tmp1.k&＃61;i;while(!q.empty()&&tmp1.num<&＃61;q.top().num)//如果说这个元素是小于栈顶的&＃xff0c;那么它里面的栈就要被更新&＃xff0c;这个元素的pre也要被更新{tmp&＃61;q.top();q.pop();if(!q.empty())q.top().next&＃43;&＃61;tmp.next;tmp1.pre&＃43;&＃61;tmp.pre;ans&＃61;tmp.num*(str[tmp.k&＃43;tmp.next-1]-str[tmp.k-tmp.pre]);if(ans>&＃61;sum){sum&＃61;ans;x&＃61;tmp.k-tmp.pre&＃43;1;y&＃61;tmp.k&＃43;tmp.next-1;}}q.push(tmp1);}while(!q.empty()){tmp&＃61;q.top();q.pop();if(!q.empty())q.top().next&＃43;&＃61;tmp.next;ans&＃61;tmp.num*(str[tmp.k&＃43;tmp.next-1]-str[tmp.k-tmp.pre]);if(ans>&＃61;sum){sum&＃61;ans;x&＃61;tmp.k-tmp.pre&＃43;1;y&＃61;tmp.k&＃43;tmp.next-1;}}printf("%lld\n%lld %lld\n",sum,x,y);return 0;
}