记录编号	200742	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战II]燃灵之链	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.150 s
提交时间	2015-10-29 14:24:45	内存使用	0.34 MiB

#include<cstdio>
#include<iostream>
using namespace std;
const int SIZEN=10010,SIZEK=1010,INF=0x7fffffff/2;
typedef long long LL;
int N,K;
LL f[SIZEK][2]={0};//0代表不选，1代表选
LL g[SIZEK][2]={0};
void read()
{
	scanf("%d%d",&N,&K);
	int a;
	scanf("%d",&a);
	for(int i=0;i<=K;i++) g[i][1]=-INF,g[i][0]=-INF,f[i][1]=-INF,f[i][0]=-INF;
	f[1][0]=-INF;f[1][1]=a;
	for(int i=2;i<=N;i++)
	{
		int L=(i+1)/2;
		scanf("%d",&a);
		for(int j=1;j<=K&&j<=L;j++)
		{
			g[j][0]=max(f[j][0],f[j][1]);
			if(j==1) g[j][1]=max((LL)a,f[j][1]+a);
			else g[j][1]=max(f[j-1][0]+a,f[j][1]+a);
		}
		//cout<<i<<endl;
		for(int j=0;j<=K&&j<=L;j++)
		{
			f[j][0]=g[j][0];
			f[j][1]=g[j][1];
			//cout<<j<<" "<<f[j][0]<<" "<<f[j][1]<<endl;
		}
	}
	int ans;
	ans=max(g[K][0],g[K][1]);
	printf("%d",ans);
}
int main()
{
	freopen("KPengshuangcang.in","r",stdin);
	freopen("KPengshuangcang.out","w",stdout);
	read();
	return 0;
}