表示 sca for img limit line -- amp
* Line 1: 牛的数量 N。
* Lines 2..N+1: 第 i+1 是一个整数,表示第i头牛的高度。
* Line 1: 一个整数表示c[1] 至 c[N]的和。
- #include < cstdio > const int maxn = 80000 + 10;
- int h[maxn],
- sta[maxn],
- top = 0;
- int main() {
- int n;
- scanf("%d", &n);
- for (int i = 1; i <= n; i++) scanf("%d", h + i);
- h[n + 1] = 1 << 30;
- sta[top = 1] = n + 1;
- long long ans = 0;
- for (int i = n; i; i--) {
- while (top && h[i] > h[sta[top]]) top--;
- ans += sta[top] - i - 1;
- sta[++top] = i;
- }
- printf("%lld\n", ans);
- return 0;
- }
[BZOJ1660][Usaco2006 Nov]Bad Hair Day 乱发节
来源: http://www.bubuko.com/infodetail-2296723.html