BZOJ 1233:[Usaco 2009 Open]干し草の山tower|ダイナミックプランニング

上から列挙する
現在の層を最もやせさせる
まったく神題だが,できないわけではない.

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<iostream>
#define T 110005
using namespace std;
int sc()
{
	int i=0; char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
	return i;
}
int a[T],n,q[T],f[T],g[T];
int main()
{
	n=sc();
	for(int i=1;i<=n;i++)a[i]=a[i-1]+sc();
	int l=1,r=1;q[1]=n+1;
	for(int i=n;i>0;i--)
	{
		while(l<r&&a[q[l+1]-1]-a[i-1]>=f[q[l+1]])l++;
		f[i]=a[q[l]-1]-a[i-1];
		g[i]=g[q[l]]+1;
		while(l<r&&a[q[r]-1]-a[i-1]<f[q[r]]-f[i])r--;
		q[++r]=i;
	}
	cout<<g[1];
	return 0;
}