poj 3250 单调栈 *

题意：一群高度不完全相同的牛从左到右站成一排，每头牛只能看见它右边的比它矮的牛的发型，若遇到一头高度大于或等于它的牛，则无法继续看到这头牛后面的其他牛。

给出这些牛的高度，要求每头牛可以看到的牛的数量的和。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 #include<stack>
 9 using namespace std;
10 #define MOD 1000000007
11 const int INF=0x3f3f3f3f;
12 const double eps=1e-5;
13 typedef long long ll;
14 #define cl(a) memset(a,0,sizeof(a))
15 #define ts printf("*****
");
16 const int MAXN=80005;
17 int n,m,tt;
18 int st[MAXN];
19 int main()
20 {
21     int i,j,k;
22     #ifndef ONLINE_JUDGE
23     freopen("1.in","r",stdin);
24     #endif
25     while(~scanf("%d",&n))
26     {
27         int top=0;
28         ll sum=0;
29         for(i=0;i<n;i++)
30         {
31             int a;
32             scanf("%d",&a);
33             while(top>0&&st[top-1]<=a)   top--;
34             sum+=top;
35             st[top++]=a;
36         }
37         printf("%lld
",sum);
38     }
39 }