這題大意就是一排高低參差不齊的牛 歪脖子 只能往右看 而且只能看到比自己矮的 碰到高的視線都被擋住了 就問各位牛加起來看到的牛多少只

N最大80000 硬搞O(n^2)? 顯然不行 要去掉那些冗余操作

設(shè)f[i]表示在i+1..n中，第一個比i高的牛，則可以通過f[i]的轉(zhuǎn)移，減少每次掃描的操作，這樣就可以達到減少冗余的目的了

上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);
??
??? }
}