记录编号	22294	评测结果	AAAAAAAWAA
题目名称	拯救	最终得分	90
用户昵称	Pom	是否通过	未通过
代码语言	C++	运行时间	0.153 s
提交时间	2010-11-18 15:20:05	内存使用	7.30 MiB

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

using namespace std;

const int MAXN=1022;

int n,i,j,k,a[MAXN],f[MAXN][2][601],q[MAXN][601];
char st[MAXN];

void init()
{
	freopen("savey.in","r",stdin);
	freopen("savey.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d",&a[i]);
}

void solve()
{
	q[1][1]=1;
	for (i=2;i<=n;i++)
	{
		for (j=1;j<=600;j++)
			q[i][j]=(q[i-1][j]+q[i-1][j])%10000+(q[i-1][j-1]+q[i-1][j-1])/10000;
		q[i][1]++;
		for (j=2;j<=600;j++)
			q[i][j]+=q[i][j-1]/10000;
	}
	if (a[1]==1)
	{
		f[1][1][1]=0;
		f[1][0][1]=1;
	}
	else
	{
		f[1][1][1]=1;
		f[1][0][1]=0;
	}
	for (i=2;i<=n;i++)
	{
		if (a[i]==1)
		{
			for (j=1;j<=600;j++)
				f[i][0][j]=(f[i-1][1][j]+q[i-1][j])%10000+(f[i-1][1][j-1]+q[i-1][j-1])/10000;
			f[i][0][1]++;
			for (j=2;j<=600;j++)
				f[i][0][j]+=f[i][0][j-1]/10000;
			//f[i][0]=f[i-1][1]+q[i-1]+1;
			for (j=1;j<=600;j++)
				f[i][1][j]=f[i-1][0][j];
			//f[i][1]=f[i-1][0];
		}
		else
		{
			for (j=1;j<=600;j++)
				f[i][1][j]=(f[i-1][1][j]+q[i-1][j])%10000+(f[i-1][1][j-1]+q[i-1][j-1])/10000;
			f[i][1][1]++;
			for (j=2;j<=600;j++)
				f[i][1][j]+=f[i][1][j-1]/10000;
			//f[i][1]=f[i-1][1]+1+q[i-1];
			for (j=1;j<=600;j++)
				f[i][0][j]=f[i-1][0][j];
			//f[i][0]=f[i-1][0];
		}
	}
	j=400;
	while (!f[n][0][j] && j)
	{
		j--;
	}
	printf("%d",f[n][0][j]);
	j--;
	for (;j>0;j--)
	{
		if (f[n][0][j]<1000) printf("0");
		if (f[n][0][j]<100) printf("0");
		if (f[n][0][j]<10) printf("0");
		printf("%d",f[n][0][j]);
	}
	printf("\n");
}

int main()
{
	init();
	solve();
	return 0;
}