poj3250（单调栈）

Bad Hair Day

题意：

　　有n头奶牛，每头奶牛可以看见比它矮的牛（只能向右看），求n头奶牛看见的奶牛数之和。

分析：

　　用单调栈维护相邻奶牛高度减小的序列，找出每头奶牛可以看见奶牛的右边界。

代码：

#include <stack>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;
#define ll long long
#define ull unsigned long long
#define cls(x) memset(x,0,sizeof(x))
#define clslow(x) memset(x,-1,sizeof(x))

const int maxn=1e5+100;

int n;

stack<int>st;
int cow[maxn],R[maxn];

int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++){
            scanf("%d",&cow[i]);
        }

        while(!st.empty())  st.pop();
        for(int i=n;i>=1;i--){
            while(st.size()&&cow[st.top()]<cow[i])  st.pop();

            if(st.empty())  R[i]=n+1;
            else            R[i]=st.top();

            st.push(i);
        }

        ll sum=0;
        for(int i=1;i<=n;i++){
            sum+=(R[i]-i-1);
        }
        printf("%lld
",sum);
    }
    return 0;
}