记录编号	168286	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO Open09] 干草堆	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.076 s
提交时间	2015-07-03 10:23:00	内存使用	1.46 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
const int SIZEN=100010,INF=0x7fffffff/2;
int N;
int sum[SIZEN]={0};
int F[SIZEN]={0};
int nxt[SIZEN]={0};
deque<int> Q;
int calc(int k){
	return sum[k-1]-F[k];
}
int back2(const deque<int> &Q){
	return Q[Q.size()-2];
}
void work(void){
	F[N+1]=0;
	Q.push_front(N+1);
	for(int i=N;i>=1;i--){
		while(Q.size()>=2&&calc(back2(Q))>=sum[i-1]) Q.pop_back();
		F[i]=sum[Q.back()-1]-sum[i-1];
		nxt[i]=Q.back();
		while(Q.size()&&calc(i)>=calc(Q.front())) Q.pop_front();
		Q.push_front(i);
	}
	int ans=0,x=1;
	while(x<=N){
		x=nxt[x];
		ans++;
	}
	printf("%d\n",ans);
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		scanf("%d",&sum[i]);
		sum[i]+=sum[i-1];
	}
}
int main(){
	freopen("tower.in","r",stdin);
	freopen("tower.out","w",stdout);
	read();
	work();
	return 0;
}