http://poj.org/problem?id=2796
题意：求n个数的和乘以这n个数中的最小值的积最大的数，以及其范围。
思路：求每一个数两边的比其大的数的和，再乘以这个数。还有一个范围，用单调栈找以及记录。
这个题和2559差不多，就是多了一个对数字的求和。
1 #include <stdio.h> 2 #include <iostream> 3 #include <stack> 4 5 #define x 100010 6 7 using namespace std; 8 9 stack<long long >s; 10 long long l[x],r[x],a[x],sum,ans,z[x],m,loc; 11 12 int main(){ 13 int n; 14 scanf("%d",&n); 15 ans=0; 16 z[0]=0,r[0]=1,l[0]=1,l[1]=1,r[n]=n; //要考虑案例是1 0 的情况。 17 for(int i=1;i<=n;i++){ 18 19 scanf("%lld",&a[i]); 20 z[i]+=z[i-1]+a[i]; //z[m]-z[n-1]就是从m到n的a[i]之和。 21 } 22 a[0]=-1,a[n+1]=-1; 23 while(!s.empty()){ 24 25 s.pop(); 26 } 27 s.push(0); 28 29 for(int i=1;i<=n;i++){ 30 31 for(m=s.top();a[m]>=a[i];m=s.top()) 32 33 s.pop(); 34 35 l[i]=m+1; 36 37 s.push(i); 38 } 39 while(!s.empty()) 40 41 s.pop(); 42 43 s.push(n+1); 44 45 for(int i=n;i>0;i--){ 46 sum=0; 47 48 for(m=s.top();a[m]>=a[i];m=s.top()) 49 s.pop(); 50 r[i]=m-1; 51 s.push(i); 52 if((z[r[i]]-z[l[i]-1])*a[i]>ans) {ans=(z[r[i]]-z[l[i]-1])*a[i];loc=i;} 53 } 54 55 printf("%lld\n%lld %lld\n",ans,l[loc],r[loc]); 56 return 0; 57 }