题目链接:http://poj.org/problem?id=2796
题目大意：给定一个长度为n的序列，让你在n个数中取一段连续的区间，使这个区间中的最小值乘以这个区间元素和的值最大，并输出左右端点
对于每一个数 ai ，作为某一段区间的最小值，求出保证 ai 最小，它最左可以扩展到 Li ,最右可以扩展到 Ri 暴力的话需要 n2 ，这样显然是超时的 我们可以用单调递增栈来维护，从左到右考虑每一个新加入的数 ai ，如果能使栈中数 x 弹出，则数x最右可以扩展到 i−1 (因为如果前面还有比它小的数，数 x 就不会存在于栈中)，这样我们就可以求出每个数i向右可以扩展的最远距离 Ri ,求 Li 只需将该过程反过来即可 统计答案可以用前缀和 q[] 来统计，则每一个数作为最小值的答案就是 a[i]∗(q[R[i]]−q[L[i]−1]) 注意答案有0的情况，可以讲ans初始为-1，也可以讲答案更新条件改成 a[i]∗(q[R[i]]−q[L[i]−1])≥ans 还有这道题爆int 代码如下：
#include<algorithm> #include<cstdio> #define N 100050 #define int long long //注意这道题爆int using namespace std; int a[N],L[N],R[N],q[N],n,top,ans,l,r; struct Data{ int x,k; Data(int _=0,int __=0):x(_),k(__){} }s[N]; main(){ ans=-1; scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld",a+i),q[i]=q[i-1]+a[i]; for(int i=1;i<=n;i++){ if(!top) {s[++top]=Data(i,a[i]);continue;} if(a[i]>=s[top].k); else while(a[i]<s[top].k && top) R[s[top--].x]=i-1; s[++top]=Data(i,a[i]); }//求R数组 while(top) R[s[top--].x]=n;//注意这里要将没出栈的元素R值赋为n for(int i=n;i>=1;i--){ if(!top) {s[++top]=Data(i,a[i]);continue;} if(a[i]>=s[top].k); else while(a[i]<s[top].k && top) L[s[top--].x]=i+1; s[++top]=Data(i,a[i]); }//求L数组 while(top) L[s[top--].x]=1;//同上 for(int i=1;i<=n;i++) if(a[i]*(q[R[i]]-q[L[i]-1])>ans){//统计答案，如果ans初值为0，将>ans改为>=ans即可 ans=a[i]*(q[R[i]]-q[L[i]-1]); l=L[i];r=R[i]; } printf("%lld",ans); printf("\n%lld %lld\n",l,r); return 0; }