记录编号	23367	评测结果	AAAAAAAAAA
题目名称	[AHOI2009] 跳棋	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2011-03-09 13:59:00	内存使用	0.28 MiB

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;
const long long oo=100000000000000001LL;
int a[1001];
int h,n;
long long f1[1005],f2[1005],ans;
void init()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
		if (i==1) a[1]=0;
		if (a[i]!=0 && a[i-1]!=0)
		{
			h++;
		}
	}
}

void solve0()
{
	int t1=0,t2=0;
	for (int i=1;i<=n;i++)
	if ((i & 1)==0)
	{
		if (a[i]!=0) t2++;
		else t1++;
	}
	printf("%d %d\n",t1,t2);
}

void solve1()
{	
	printf("0 ");
	for (int i=1;i<=n;i++)
	{
		f1[i]=oo;
		if (i>2 && f1[i-1]!=oo && f1[i-2]!=oo)
		{
			f1[i]=f1[i-1]+f1[i-2];
		}
		if (f1[i]>oo) f1[i]=oo;
		if (a[i]!=0) f1[i]=1;
	}
	for (int i=n;i>=2;i--)
	{
		f2[i]=oo;
		if (i<=n-2 && f2[i+1]!=oo && f2[i+2]!=oo)
		{
			f2[i]=f2[i+1]+f2[i+2];
		}
		if (f2[i]>oo) f2[i]=oo;
		if (a[i]!=0) f2[i]=1;
	}
	for (int i=2;i<n;i+=2) ans+=min(f1[i],f2[i]);
	printf("%lld\n",ans);
}

int main()
{
	freopen("checker09.in","r",stdin);
	freopen("checker09.out","w",stdout);
	init();
	if (h==0) solve0();
	else solve1();
	return 0;
}