首页 > 代码库 > BZOJ 1660: [Usaco2006 Nov]Bad Hair Day 乱发节
BZOJ 1660: [Usaco2006 Nov]Bad Hair Day 乱发节
Description
Input
* Line 1: 牛的数量 N。
* Lines 2..N+1: 第 i+1 是一个整数，表示第i头牛的高度。
Output
* Line 1: 一个整数表示c[1] 至 c[N]的和。
题解：
BZOJ服务器好像有问题，图片很不好显示，看上面的就好了。
设牛i看到的最远位置是see[i]。
从前向后扫，求see值，设前面有一头牛A,后面有一头牛B，如果h[B]>=h[A]，那么A这头牛就永远不可能成为B牛后面的牛的see值。
可以用单调栈维护这个单调性，
从前向后扫，当栈顶牛高度小于当前牛高度时退栈，之道栈顶牛高度>=当前牛高度，那么这个栈顶牛就是当前牛的see值，将当前牛入栈。
ans=∑(see[i]-i-1)。
代码：
#include<cstdio>#include<cstring>#include<algorithm>//by zrt//problem:using namespace std;const int MAXN=80005;struct N{ int x,w; N(int a=0,int b=0){ x=a,w=b; }};N stk[MAXN];int top;int see[MAXN];int n;int h[MAXN];int inf=1<<30;typedef long long LL;int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&h[i]); } stk[top++]=N(n+1,inf); for(int i=n;i>=1;i--){ while(stk[top-1].w<h[i]) top--; see[i]=stk[top-1].x; stk[top++]=N(i,h[i]); } LL ans=0; for(int i=1;i<=n;i++){ ans+=see[i]-i-1; } printf("%lld\n",ans); return 0;}
BZOJ 1660: [Usaco2006 Nov]Bad Hair Day 乱发节
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。