维护一个单调栈，保持从大到小的顺序，每次加入一个元素都将其推到尽可能栈底，知道碰到一个比他大的，然后res+=tail，说明这个cow的头可以被前面tail个cow看到。如果中间出现一个超级高的，自然会推到栈底，即此元素以前的cow看不到此元素后面cow的头，即res不会加此元素前面的个数，说明是正确的。
注意要用long long 或者 __int64类型。 刚开始看着80000不大的样子，其实最大情况下res有 1+2+....+80000 = 3200040000，超过int范围。以后还是验证一下，或者看到这种比较大的数还是优先用long long 或者 __int64类型吧。
代码：
#include <iostream> #include <cstdio> using namespace std; #define N 80007 int a[N]; int main() { int head,tail,n,x; ll res; while(scanf("%d",&n)!=EOF) { head = tail = 0; res = 0; while(n--) { scanf("%d",&x); while(tail > head && x >= a[tail-1]) tail--; a[tail++] = x; res += tail-1; } printf("%lld\n",res); } return 0; }
POJ 3250 Bad Hair Day --单调栈(单调队列?),布布扣,bubuko.com
POJ 3250 Bad Hair Day --单调栈(单调队列?)
原文：http://www.cnblogs.com/whatbeg/p/3569257.html
