记录编号	437418	评测结果	AAAAAAATTT
题目名称	[NOIP 2013]积木大赛	最终得分	70
用户昵称	swttc	是否通过	未通过
代码语言	C++	运行时间	3.074 s
提交时间	2017-08-14 09:51:06	内存使用	1.08 MiB

#include<iostream>
#include<cstdio>

using namespace std;

int h[100010],to[100010],n,ans=0x7fffffff,ro;

void outt()
{
	for(int i=1;i<=n;i++)
	{
		cout<<h[i]<<" ";
	}
}

void dfs(int l,int r)
{
	if(ro>=ans) return;
	if(r<l) return;
	ro++;
	int f=1;
	int m[100010],cnt=0;
	for(int i=l;i<=r;i++)
	{
		if(to[i]==0)
		{
			m[++cnt]=i;
			break;
		}
		h[i]++;
		if(h[i]==to[i])
		{
			m[++cnt]=i;
		}
	}
	//outt();cout<<ro<<endl;cout<<cnt<<endl;
	for(int i=1;i<=n;i++)
	{
		if(h[i]!=to[i])
		{
			f=0;
			break;
		}
	}
	if(f)
	{
		ans=min(ans,ro);
		return;
	}
	if(cnt!=0)
	{
		dfs(l,m[1]-1);
		for(int i=2;i<=cnt;i++)
		{
			dfs(m[i-1]+1,m[i]-1);
		}
		dfs(m[cnt]+1,r);
	}
	else
	{
		dfs(l,r);
	}
	return;
}

int main()
{
	freopen("BlockNOIP2013.in","r",stdin);
	freopen("BlockNOIP2013.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&to[i]);
	}
	int ff=1;
	for(int i=1;i<=n;i++)
	{
		if(to[i]!=0)
		{
			ff=0;
			break;
		}
	}
	if(ff)
	{
		cout<<0;
		return 0;
	}
	dfs(1,n);
	cout<<ans;
	return 0;
}