这题大意就是一排高低参差不齐的牛 歪脖子 只能往右看 而且只能看到比自己矮的 碰到高的视线都被挡住了 就问各位牛加起来看到的牛多少只
N最大80000 硬搞O(n^2) 显然不行 要去掉那些冗余操作
设f[i]表示在i+1..n中，第一个比i高的牛，则可以通过f[i]的转移，减少每次扫描的操作，这样就可以达到减少冗余的目的了
上CODE：
#include <stdio.h>
int n,f[80001],h[80001];
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&h[i]);
int t;
unsigned int sum = 0;
for(i=n;i>=1;i--)
{
t=0;
f[i]=i+1;
while(f[i]<=n&&h[i]>h[f[i]])
{
t+=f[f[i]]-f[i];
f[i]=f[f[i]];
}
sum+=t;
}
printf("%u\n",sum);
}
}