记录编号	196735	评测结果	AAAAAAAAAA
题目名称	[POJ2479+2593][NOIP2015初赛]双子序列最大和	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.075 s
提交时间	2015-10-22 16:11:33	内存使用	0.23 MiB

#include <cstdio>
#include <ctime>
#define N 100010
#define M 3
using namespace std;
typedef int ll;
int n,K;
ll f[M][2]={0},g[M][2]={0};
ll INF=1;
int max(int a,int b)
{
	if(a>b)return a;
	return b;
}
void read()
{
	int i;
	INF=(INF<<30);
	scanf("%d",&n);
	K=2;
	//for(i=1;i<=n;i++)scanf("%d",&a[i]);
}
void work()
{
	int i,k,limit,a;
	scanf("%d",&a);
	f[1][0]=1;f[1][1]=a;
	for(i=2;i<=n;i++)
	{
		limit=(i+1)/2;
		scanf("%d",&a);
		for(k=1;k<=K&&k<=limit;k++)
		{
			g[k][0]=max(f[k][0],f[k][1]);
			g[k][1]=max(f[k-1][0]+a,f[k][1]+a);
		}
		for(k=0;k<=K&&k<=limit;k++)
		{
			f[k][0]=g[k][0];
			f[k][1]=g[k][1];
		}
	}
}
int main()
{
	freopen("Pengshuangcang.in","r",stdin);
	freopen("Pengshuangcang.out","w",stdout);
	read();
	work();
	printf("%d\n",max(g[K][0],g[K][1]));
	return 0;
}