记录编号	48794	评测结果	AAAAAAAAAAAAAAA
题目名称	二十一点	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	0.081 s
提交时间	2012-11-06 16:02:54	内存使用	16.26 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
struct node{
	int s,nex;
}a[1100];
struct edge{
	int y,v,nex;
}e[800000];
bool vis[1010];
int f[1010][1010];
int aa[1010];
int dis[1010];
int queue[10000];
int DP[1010];
int n,i,j,p,k;
bool cmp(int a,int b){
	return a>b;
}
int maxx(int a,int b){
	return a>b?a:b;
}
void dfs(int i,int j,int sum1,int sum2){
	if (sum2>21){
		f[i][j]=maxx(f[i][j],0);
		return;
	}
	bool judge=false;
	if (sum1<=16 && j<n){
		judge=true;
		sum1+=aa[++j];
		if (sum1>21){
			f[i][j]=maxx(f[i][j],1);
			return;
		}
	}
	if (judge){
		if (j<n)
		dfs(i,j+1,sum1,sum2+aa[j+1]);
		while (sum1<=16 && j<n){
				sum1+=aa[++j];
			}
		if (sum1>21){
				f[i][j]=maxx(f[i][j],1);
				return ;
			}
		if (sum1>=sum2)	f[i][j]=maxx(f[i][j],0);
		if (sum1<sum2)  f[i][j]=maxx(f[i][j],1);
		return;
	}
	if (!judge){
		if (sum1<sum2) {f[i][j]=maxx(f[i][j],1); return;}
		if (sum1>=sum2)	f[i][j]=maxx(f[i][j],0);
		if (j<n)dfs(i,j+1,sum1,sum2+aa[j+1]);
	}
}/*
void dfs(int i,int j,int sum1,int sum2){
	if (sum2>21){
		if (f[i][j]!=1)f[i][j]=-1;
		return;
	}
	//if (sum1>=sum2) f[i][j]=-1;
	//if (sum1<sum2)  f[i][j]=1;
	bool judge=false;
	if (sum1<=16){
		if (j<n){
			judge=true;
			sum1+=aa[++j];
			if (sum1>21){
				f[i][j]=1;
				return ;
			}
		}
	}
		if (j<n)	dfs(i,j+1,sum1,sum2+aa[j+1]);
		if (judge){
			while (sum1<=16 && j<n){
				sum1+=aa[++j];
			}
			if (sum1>21){
				f[i][j]=1;
				return ;
			}
			if (sum1>=sum2)	
				if (f[i][j]!=1)f[i][j]=-1;
			if (sum1<sum2)  f[i][j]=1;
		}
		//if (!judge){
		//		if (sum1>=sum2) f[i][;;/jjkx]=-1;
		//		if (sum1<sum2)  f[i][j]=1;
		//}
		if (!judge){
			while (sum2<=21 && j<n){
				if (sum1>=sum2)
				if (f[i][j]!=1)f[i][j]=-1;	
				if (sum1<sum2)  f[i][j]=1;
				sum2+=aa[++j];
			}
			if (sum2>21){
				if (f[i][j]!=1)f[i][j]=-1;
				f[i][j]=-1;
				return;
			}
		}
}*/
void add(int x,int y,int v){
	p++;
	a[x].s++;
	e[p].y=y;
	e[p].v=v;
	e[p].nex=a[x].nex;
	a[x].nex=p;
}
void SPFA(int s){
	int t;
	int tmp;
	memset(vis,true,sizeof(vis));
	memset(dis,1,sizeof(dis));
	memset(queue,0,sizeof(queue));
	vis[s]=false;
	dis[s]=0;
	int head=0;
	int tail=1;
	queue[tail]=s;
	while (head<=tail){
		head++;
		tmp=queue[head];
		vis[tmp]=true;
		t=a[tmp].nex;
		for (int i=1;i<=a[tmp].s;i++){
			if (dis[tmp]+e[t].v<dis[e[t].y]){
				dis[e[t].y]=dis[tmp]+e[t].v;
				if (vis[e[t].y]){
					vis[e[t].y]=false;
					queue[++tail]=e[t].y;
				}
			}
			t=e[t].nex;
		}
	}
}

int main()
{
	freopen("jack.in","r",stdin);
	freopen("jack.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d",&aa[i]);
	memset(f,-1,sizeof(f));
	for (i=1;i<=n-5;i++){
		dfs(i,i+3,aa[i]+aa[i+2],aa[i+1]+aa[i+3]);
	}
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++){
			if (f[i][j]==0) add(i,j+1,0);
			if (f[i][j]==1) add(i,j+1,-1);
		}
		
	memset(DP,-1,sizeof(DP));
	DP[0]=0;
	for (i=1;i<=n;i++)
		for (j=0;j<i;j++){
				if (f[j+1][i]>=0)
					if (DP[i]<0 && DP[j]>=0) DP[i]=0;
				if (DP[i]>=0)
					DP[i]=maxx(DP[i],f[j+1][i]+DP[j]);
		}
	int maxn=0;
	for (i=n;i>n-6;i--)
		maxn=maxx(maxn,DP[i]);
	printf("%d\n",maxn);
	//SPFA(1);
	//maxn=0;
	//for (i=n;i>n-6;i--)
	//	if (dis[i]<maxn) maxn=dis[i];
	//printf("%d",-maxn);
	return 0;
}