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

// KZ's
#include <fstream>
using namespace std;
#define INF 0x7fffffff
int f[10002][1002][2]={0};
int main() {
	ifstream fin ("KPengshuangcang.in");
	ofstream fout ("KPengshuangcang.out");
	int N,K;
	fin>>N>>K;
	int mp[10003]={0};
	for (int i=1;i<=N;i++)
		fin>>mp[i];
	for (int i=0;i<=N;i++)
		for (int k=0;k<=K;k++)
			f[i][k][0]=f[i][k][1]=-INF;
	for (int i=0;i<=N;i++)
		f[i][0][0]=0;
	for (int i=1;i<=N;i++)
		for (int k=1;k<=(i+1)/2&&k<=K;k++) {
			if (k<=i/2)
				f[i][k][0]=max(f[i-1][k][0],f[i-1][k][1]);
			if (k<=(i+1)/2)
				f[i][k][1]=max(f[i-1][k][1],f[i-1][k-1][0])+mp[i];
		}
	fout<<max(f[N][K][0],f[N][K][1])<<endl;
	return 0;
}
// UBWH